Number theory - 2021-09-22

« first day (2833 days earlier) ← previous day next day → last day (1239 days later) »

Spectre

07:13

@MartinSleziak I have a small doubt... would you mind helping me?

It's regarding proofs about divisibility

I have tried doing problems like "Prove $n- 1 \mid n^k - 1$ etc., but if something like "Prove that $\exists m,n : k \mid 2m + 3n \forall k$", how am I supposed to proceed?

@Euler2 I guess maybe you can help, if you're free now

Martin Sleziak

@Spectre I do not actually understand the formulation of the problem. Writing "Prove that $\exists m,n : k \mid 2m + 3n \forall k$" seems rather ambiguous.

Spectre

@MartinSleziak Well, it's just a rough type-up

Martin Sleziak

But it's very unclear what you're trying to say.

Spectre

I thought you'd just take it as an example (even if it's incomplete)

Martin Sleziak

In any case, it should be relatively easy to show that every integer can be written as $2m+3n$ for some $m,n\in\mathbb Z$.

Spectre

07:20

@MartinSleziak It's not that, it's about that there exists such pairs of $m,n$ for any integer $k$

Martin Sleziak

In fact, if you learned Bézout's identity, this is an immediate consequence of the fact that $\gcd(2,3)=1$.

Spectre

I just put that question as a hint to the type of problems I'm talking about

Martin Sleziak

@Spectre Well, this is answered by what I said, isn't it? For any integer $k$ there exists $m,n\in\mathbb Z$ such that $2m+3n=k$.

Spectre

@MartinSleziak I didn't actaully understand that

The way of solving, I meant

Martin Sleziak

If $k=2m+3n$, then obviously $k\mid 2m+3n$.

Are m,n allowed to be integers? Or is it about m,n being positive integers - that would be a bit different problem.

Spectre

07:22

@MartinSleziak I understood that one, but still I'm in the dark as to prove how I can do the proof

Martin Sleziak

Proof of what? That every integer can be written in the form $2m+3n$?

Spectre

@MartinSleziak it's an example problem sir :D... I wanted to know the way of solving of such problems

Martin Sleziak

Please, do not call me sir.

Spectre

@MartinSleziak Oh, okay, but I'm not of your age perhaps, so I thought I'd call you so.. sorry if I did it wrong ':)

Martin Sleziak

As I said, if you already learned Bézout's identity, than this should be obvious almost immediately. You have integers such that $2m+3n=1$ and you just multiply both sides by $k$.

If you haven't learned this you can try induction.

1. First you can try whether you can write k=1,2,3,4,5 is the form k=2m+3n. (I.e., you try this for a few small numbers.)

Spectre

07:25

@MartinSleziak Oh okay, so basically since $\gcd(2,3) = 1$, we see that 1 is the least element of the set $\lbrace 2m + 3n : m,n \in \mathbb{N}\rbrace$ and the subsequent elements are the possible $k$'s....

@MartinSleziak Yeah that's one thing I needed to know...

Martin Sleziak

2. Now you can try to show by induction, that if it is true for numbers up to $k$, then it is true also for $k+1$.

3. If you have shown it using induction for positive integers, then you should be extend the result to all integers.

Spectre

I usually tried induction on progressions and inequalities, so I was a bit confused as to how I can do it here

Also what should I do if it's something like this:math.stackexchange.com/questions/4256940/…

Not looking forward to answer it but I needed to understand the problem

Or say, how I can prove it

Martin Sleziak

For benefit of those reading this, the question is: Prove that for every positive integer $k$ there exist integers $n$ and $m$ such that $4n^2+9m^2-1$ is divisible by $k$.

Spectre

Well I am not actually looking forward to put an answer for it though

I wanted to learn how I can prove such questions as well, so I just asked...

Martin Sleziak

This is something where I do not see solution immediately. Let's hope that somebody else notices your question here.

Spectre

07:30

@MartinSleziak Well, I guess I understood a bit of what you said for the linear case. Thanks for that. Using induction was a bit dubious to me though

Martin Sleziak

Ok, if you try to do that by induction and you have problems, you can always ask here (or elsewhere).

Of course, I cannot promise that I'll have time to look at that - but still, it's possible that somebody notices your message in chat.

See you later!

Of course the problem with 2m+3n was much simpler - the induction works there because we're proving that $k=2m+3n$ rather than $k\mid 2m+3n$.

Spectre

It's not like I can't try proving using induction or that I haven't learnt it. I basically wanted to understand how I can use induction in cases where we don't obviously see a continuum

@MartinSleziak Yeah, thanks for that... I was blinded by some sort of false belief that there is some big sort of math required :D

Martin Sleziak

For the problem about $k\mid 4n^2+9m^2-1$, I doubt that induction on $k$ would be actually helpful.

Spectre

@MartinSleziak Could be so, but I found it dubious since I couldn't see any continuum (meaning I can't see a way of generalising it for all integers )

Martin Sleziak

Using the phrase continuum is a bit confusing to me - but maybe I simply haven't seen it in this context.

Spectre

07:37

@MartinSleziak Oh well, I should better use 'generalising' and all that... :D

Martin Sleziak

Anyway, I have some stuff to do IRL. Have a nice day!

Spectre

Yeah I was obviously foolish for having used a predefined term for something I needed to express

@MartinSleziak Yeah byeee... hope I didn't waste your time

I was a bit messy since I'm still learning

There was this one question about using induction :math.stackexchange.com/questions/4255113/…