At 30:00 the correct equation is 111(496) + 1001(-55) = 1. The first addend is corrected later, but the second is not, even if is irrelevant for the rest of the computations.
3:00 In relation to mod 3, I think it's interesting to think of the possibilities as 0, 1, and -1 (i.e. -1 is congruent to 2 mod 3). The reason is it makes it obvious that there is going to be some symmetry involving the 1 and -1 when, for example, you're constructing multiplication tables or power tables mod 3. Similarly, when you work mod 2k+1, I think it's useful to think of the possible results as being from the set {-k, -k+1, ... -1, 0, 1, ... k-1, k}, because as above, you'll see symmetries between the positive and negative values. Likewise if you work mod 2k, then something like {-k+1, ..., -1,0,1, ..., k-1, k} has a similar sort of symmetry. For example, in that first multiplication table mod 6, instead of the top row being x = 0, 1, 2, 3, 4, 5, try instead x = -2, -1, 0, 1, 2, 3. Then that first row for 2x looks like ｘ |－２ －１ ０ １ ２ ３ ２ｘ | ２ －２ ０ ２ －２ ０ Meaning when you multiply by 2 mod 6 your possible answers are just -2, 0, or 2 (which is analogous to how mod 3 can only give you results congruent to -1, 0, or 1).
I agree - it should be compulsory for any math student to construct tables in modulo n for first 10 (?) numbers based for operators multiply add. Many things become clearer. And your point about -1 mod n is well made my friend EDIT as a ps: doing stuff like this 𝐚𝑥 ≡ 𝐛 ∄ ∆ ∇ ∞ ∈ ⊨ is easy - see my post above for an easy (cost free?) way to do it. It does take a bit of time though as math unicode pdf files are a bit lengthy And I suppose html code might jiggle things up a bit as well as regional settings but - life is wonderful!
Your favorite number theory is reasonably priced (I've found it for around 40usd) but the shipping costs out of Europe are typically more than the book. (I would not be surprised if they haven't all been bought up by 3rd party sellers to be obscenely marked up in price.)
Iirc, you are guaranteed a solution when gcd(a,n)=1 because there is a unique multiplicative inverse for a (mod n). If gcd(a,n) = gcd(b,n), then you can also find a solution I believe.
The equation 2x=6 mod (12) shows that you do not need gcd(a,n)=gcd(b,n) in the case where gcd(a,n) is not equal to 1. It is enough that gcd(b,n) is a multiple of gcd(a,n). :)
@@tracyh5751 ah, yes. I was commenting from memory, I studied number theory a few years ago and primarily focus on (complex) analysis currently. Could use some touching up on my number theory I guess haha.
@@GhostyOcean To be fair to yourself, what you said wasn't wrong. And it's quite possible that the weaker version you said was once useful to you in a proof.
I proceed to prove the uniqueness statement (the HW exercise). From ax=b (mod n) (1). We have that if x0 is a solution of ax=b (mod n) then gcd(a,n)=:d | b (proven by Michael). That is, a=a0d, b=b0d and n=n0d for some a0, b0, n0 natural numbers. We can now write the equation as a0dx0 = b0d (mod n0d), with gcd(a0, n0) = 1 because d was the GREATEST common factor of a and n (for when we divide a and n by d there are no common factors left, and a0 and n0 must now be relatively prime). Now, from a0dx0 = b0d (mod n0d) we have, by definition of congruence, that a0dx0-b0d=kn0d for some k integer. Dividing by d we get a0x0-b0=kn0 or a0x0=b0 (mod n0) (*). (*) has only one solution: x0. This is because gcd(a0, n0)=1 so the solution must lie in ONE of the {1, 2, ..., n0-1} residues mod n0. The solution cannot be a multiple of n0 because then a0x = 0 (mod n0) but we know that b0=/=0. Setting x0 the solution of (*), which is also a solution of the original equation (1), then x1=x0+n0, x2= x0+2n0, x3=x0+3n0,....x_(d-1)=x0+(d-1)n0 satisfy the equation (*) but are all the "same solution" as x0: they are all congruent to x0 mod n0. Note that all the x_k=x0+kn0 satisfy (1) too: a(x0+kn/d)=ax0+akn/d=b+akn/d=b+a0kn=b mod n (for a/d=a0). But look at this. We know that n0=n/d. Therefore we can write the statement above as x0, x0+n/d, x0+2n/d, x0+3n/d,..., x0+(d-1)n/d. BUT NOW THESE NUMBERS ARE NOT congruent mod n (not mod n0); they are not longer the same solution (mod n). So these must be DIFFERENT solutions of (1). Observe that x0+dn/d = x0+n is indeed congruent to x0 mod n (and x0+(d+k)n/d for all k such that 0
Wait, what? No, there aren't only gcd(a, n) solutions, there are infinitely many! There are, in fact, solutions for all integer k such that x_k = x_0 + k·n/gcd(a,n) For example, in the case 2x=4 mod 6, there is x=2, 5, 8, 11,... as solutions.
Michael, as i've said already there are infinitely many solutions, not only gcd(a,n) solutions. In the first examples this can be clearly seen, but also in the example just after you skip the uniqueness proof (??????): 10x=6 mod (12) has also x=15 as a solution! It has x=3, 9, 15, 21, 27... 3+6k for all k as solutions!
I think it means "only gcd(a,n) solutions" in the set [0,1,...,n-1], since after reducing mod n, all integers are equivalent to that set. Sorry for bad English.
A good question that has been well answered by another which brings a deeper understanding and that is: is the number 3 confined to "only gcd(a,n) solutions" defines a solution that does indeed extend to a range of solutions that are different in one respect yet are exactly same in another respect? What is an equivalence class mod n? Are there some trig functions that show behavior like that - say 𝟤𝛑 or even (mod 𝟤𝛑)?
@@Alan-zf2tt I proceed to prove the uniqueness statement (the HW exercise). From ax=b (mod n) (1). We have that if x0 is a solution of ax=b (mod n) then gcd(a,n)=:d | b (proven by Michael). That is, a=a0d, b=b0d and n=n0d for some a0, b0, n0 natural numbers. We can now write the equation as a0dx0 = b0d (mod n0d), with gcd(a0, n0) = 1 because d was the GREATEST common factor of a and n (for when we divide a and n by d there are no common factors left, and a0 and n0 must now be relatively prime). Now, from a0dx0 = b0d (mod n0d) we have, by definition of congruence, that a0dx0-b0d=kn0d for some k integer. Dividing by d we get a0x0-b0=kn0 or a0x0=b0 (mod n0) (*). (*) has only one solution: x0. This is because gcd(a0, n0)=1 so the solution must lie in ONE of the {1, 2, ..., n0-1} residues mod n0. The solution cannot be a multiple of n0 because then a0x = 0 (mod n0) but we know that b0=/=0. Setting x0 the solution of (*), which is also the solution of the original equation (1), then x1=x0+n0, x2= x0+2n0, x3=x0+3n0,....x_(d-1)=x0+(d-1)n0 satisfy the equation (*) but are all the "same solution" as x0: they are all congruent to x0 mod n0. But look at this. We know that n0=n/d. Therefore we can write the statement above as x0, x0+n/d, x0+2n/d, x0+3n/d,..., x0+(d-1)n/d. BUT NOW THESE NUMBERS ARE NOT congruent mod n (not mod n0); they are not longer the same solution (mod n). So these must be DIFFERENT solutions of (1). Observe that x0+dn/d = x0+n is indeed congruent to x0 mod n (and x0+(d+k)n/d for all k such that 0
A little bit off topic but helpful (?) (I hope) EDIT: tried to solve ambiguities on my use of '+' if you want to do stuff like this 𝐚𝑥 ≡ 𝐛 ∄ ∆ ∇ ∞ ∈ ⊨ ∃ ℐ ℒ Ƞ ∠ then geany can be used to output unicode that can be copied and pasted into documents and websites Method that works for me in Geany is press ctrl+shift u (+ denoting press those keys together) release u+ctrl+shift (+ denoting release those keys together) then type + (+ denoting the '+' character) enter unicode using lower case letters if letters are required (code will not appear onscreen) (example type 2200) then press enter (unicode character will appear onscreen) (example unicode 2200 reveals ∀ )
number theory and congruence can really give your head a serious stir :p
13:19 It's the Well-Ordering Principle, not the Archimedean Principle.
Good catch!
15:51 MINUS, not plus!
At 30:00 the correct equation is 111(496) + 1001(-55) = 1. The first addend is corrected later, but the second is not, even if is irrelevant for the rest of the computations.
Man, this takes me back to my first year of university!
Bravo and thank for this good explanation 👍🙏
Good explanations
3:00 In relation to mod 3, I think it's interesting to think of the possibilities as 0, 1, and -1 (i.e. -1 is congruent to 2 mod 3). The reason is it makes it obvious that there is going to be some symmetry involving the 1 and -1 when, for example, you're constructing multiplication tables or power tables mod 3.
Similarly, when you work mod 2k+1, I think it's useful to think of the possible results as being from the set {-k, -k+1, ... -1, 0, 1, ... k-1, k}, because as above, you'll see symmetries between the positive and negative values. Likewise if you work mod 2k, then something like {-k+1, ..., -1,0,1, ..., k-1, k} has a similar sort of symmetry.
For example, in that first multiplication table mod 6, instead of the top row being x = 0, 1, 2, 3, 4, 5, try instead x = -2, -1, 0, 1, 2, 3. Then that first row for 2x looks like
ｘ |－２ －１ ０ １ ２ ３
２ｘ | ２ －２ ０ ２ －２ ０
Meaning when you multiply by 2 mod 6 your possible answers are just -2, 0, or 2 (which is analogous to how mod 3 can only give you results congruent to -1, 0, or 1).
I agree - it should be compulsory for any math student to construct tables in modulo n for first 10 (?) numbers based for operators multiply add.
Many things become clearer. And your point about -1 mod n is well made my friend
EDIT as a ps: doing stuff like this
𝐚𝑥 ≡ 𝐛 ∄ ∆ ∇ ∞ ∈ ⊨
is easy - see my post above for an easy (cost free?) way to do it. It does take a bit of time though as math unicode pdf files are a bit lengthy
And I suppose html code might jiggle things up a bit as well as regional settings but - life is wonderful!
@@Alan-zf2tt An even easier method that I use is just Google the symbol I want and copy paste. For instance, Google "Exists symbol" and copy paste ∃
Your favorite number theory is reasonably priced (I've found it for around 40usd) but the shipping costs out of Europe are typically more than the book. (I would not be surprised if they haven't all been bought up by 3rd party sellers to be obscenely marked up in price.)
Iirc, you are guaranteed a solution when gcd(a,n)=1 because there is a unique multiplicative inverse for a (mod n). If gcd(a,n) = gcd(b,n), then you can also find a solution I believe.
The equation 2x=6 mod (12) shows that you do not need gcd(a,n)=gcd(b,n) in the case where gcd(a,n) is not equal to 1. It is enough that gcd(b,n) is a multiple of gcd(a,n). :)
@@tracyh5751 ah, yes. I was commenting from memory, I studied number theory a few years ago and primarily focus on (complex) analysis currently. Could use some touching up on my number theory I guess haha.
@@GhostyOcean
To be fair to yourself, what you said wasn't wrong. And it's quite possible that the weaker version you said was once useful to you in a proof.
29:57 1001(-55), not 1001(-5)
I proceed to prove the uniqueness statement (the HW exercise).
From ax=b (mod n) (1).
We have that if x0 is a solution of ax=b (mod n) then gcd(a,n)=:d | b (proven by Michael). That is, a=a0d, b=b0d and n=n0d for some a0, b0, n0 natural numbers. We can now write the equation as a0dx0 = b0d (mod n0d), with gcd(a0, n0) = 1 because d was the GREATEST common factor of a and n (for when we divide a and n by d there are no common factors left, and a0 and n0 must now be relatively prime).
Now, from a0dx0 = b0d (mod n0d) we have, by definition of congruence, that a0dx0-b0d=kn0d for some k integer. Dividing by d we get a0x0-b0=kn0 or a0x0=b0 (mod n0) (*).
(*) has only one solution: x0. This is because gcd(a0, n0)=1 so the solution must lie in ONE of the {1, 2, ..., n0-1} residues mod n0. The solution cannot be a multiple of n0 because then a0x = 0 (mod n0) but we know that b0=/=0.
Setting x0 the solution of (*), which is also a solution of the original equation (1), then x1=x0+n0, x2= x0+2n0, x3=x0+3n0,....x_(d-1)=x0+(d-1)n0 satisfy the equation (*) but are all the "same solution" as x0: they are all congruent to x0 mod n0. Note that all the x_k=x0+kn0 satisfy (1) too: a(x0+kn/d)=ax0+akn/d=b+akn/d=b+a0kn=b mod n (for a/d=a0).
But look at this. We know that n0=n/d. Therefore we can write the statement above as x0, x0+n/d, x0+2n/d, x0+3n/d,..., x0+(d-1)n/d. BUT NOW THESE NUMBERS ARE NOT congruent mod n (not mod n0); they are not longer the same solution (mod n). So these must be DIFFERENT solutions of (1). Observe that x0+dn/d = x0+n is indeed congruent to x0 mod n (and x0+(d+k)n/d for all k such that 0
0:58 is 1/3=0R1
Isn't this problem related to the cyclic group Z(n)?
In which way(s)?
Wait, what? No, there aren't only gcd(a, n) solutions, there are infinitely many! There are, in fact, solutions for all integer k such that x_k = x_0 + k·n/gcd(a,n) For example, in the case 2x=4 mod 6, there is x=2, 5, 8, 11,... as solutions.
But 2 and 8 are the same solution, ditto 5 and 11, because they differ by a multiple of 6.
Linear congruences? More like "Liking this; cool it is!" 👍
32:35
Bro what
@@quantumgaming9180that’s a good place to stop
Michael, as i've said already there are infinitely many solutions, not only gcd(a,n) solutions. In the first examples this can be clearly seen, but also in the example just after you skip the uniqueness proof (??????): 10x=6 mod (12) has also x=15 as a solution! It has x=3, 9, 15, 21, 27... 3+6k for all k as solutions!
I think it means "only gcd(a,n) solutions" in the set [0,1,...,n-1], since after reducing mod n, all integers are equivalent to that set. Sorry for bad English.
A good question that has been well answered by another which brings a deeper understanding
and that is: is the number 3 confined to "only gcd(a,n) solutions" defines a solution that does indeed extend to a range of solutions that are different in one respect yet are exactly same in another respect?
What is an equivalence class mod n? Are there some trig functions that show behavior like that - say 𝟤𝛑 or even (mod 𝟤𝛑)?
@@Alan-zf2tt I proceed to prove the uniqueness statement (the HW exercise).
From ax=b (mod n) (1).
We have that if x0 is a solution of ax=b (mod n) then gcd(a,n)=:d | b (proven by Michael). That is, a=a0d, b=b0d and n=n0d for some a0, b0, n0 natural numbers. We can now write the equation as a0dx0 = b0d (mod n0d), with gcd(a0, n0) = 1 because d was the GREATEST common factor of a and n (for when we divide a and n by d there are no common factors left, and a0 and n0 must now be relatively prime).
Now, from a0dx0 = b0d (mod n0d) we have, by definition of congruence, that a0dx0-b0d=kn0d for some k integer. Dividing by d we get a0x0-b0=kn0 or a0x0=b0 (mod n0) (*).
(*) has only one solution: x0. This is because gcd(a0, n0)=1 so the solution must lie in ONE of the {1, 2, ..., n0-1} residues mod n0. The solution cannot be a multiple of n0 because then a0x = 0 (mod n0) but we know that b0=/=0.
Setting x0 the solution of (*), which is also the solution of the original equation (1), then x1=x0+n0, x2= x0+2n0, x3=x0+3n0,....x_(d-1)=x0+(d-1)n0 satisfy the equation (*) but are all the "same solution" as x0: they are all congruent to x0 mod n0.
But look at this. We know that n0=n/d. Therefore we can write the statement above as x0, x0+n/d, x0+2n/d, x0+3n/d,..., x0+(d-1)n/d. BUT NOW THESE NUMBERS ARE NOT congruent mod n (not mod n0); they are not longer the same solution (mod n). So these must be DIFFERENT solutions of (1). Observe that x0+dn/d = x0+n is indeed congruent to x0 mod n (and x0+(d+k)n/d for all k such that 0
@ 11:03 Should be k*x-l*y not l*y-k*x.
НЕТ ПУТИ 30:39 💀
😮
A little bit off topic but helpful (?) (I hope) EDIT: tried to solve ambiguities on my use of '+'
if you want to do stuff like this
𝐚𝑥 ≡ 𝐛
∄ ∆ ∇ ∞ ∈ ⊨
∃ ℐ ℒ Ƞ ∠
then geany can be used to output unicode that can be copied and pasted into documents and websites
Method that works for me in Geany is
press ctrl+shift u (+ denoting press those keys together)
release u+ctrl+shift (+ denoting release those keys together)
then type + (+ denoting the '+' character)
enter unicode using lower case letters if letters are required (code will not appear onscreen) (example type 2200)
then press enter (unicode character will appear onscreen) (example unicode 2200 reveals ∀ )