Solving linear congruences

🌟Support the channel🌟

🌟my other channels🌟

🌟My Links🌟

🌟How I make Thumbnails🌟

🌟Suggest a problem🌟

[kkanden]

number theory and congruence can really give your head a serious stir :p

[mizarimomochi]

13:19 It's the Well-Ordering Principle, not the Archimedean Principle.

[MarcoMate]

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.

[xizarrg]

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.)

[GhostyOcean]

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.

[alimokadem]

Bravo and thank for this good explanation 👍🙏

[lewisbulled]

Man, this takes me back to my first year of university!

[Bodyknock]

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).

[r.maelstrom]

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: 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<k<=d-1 are all the same solution mod n as x0+kn/d). So it IS the same solution as x0 mod n: apparently we got all the different solutions of (1) and there are d of them.

Are there some more that we have forgotten? Suppose y is another solution of (1). Then ay=ax=b mod n. Therefore ay-ax=0 (mod n), and a(y-x)=0 mod n iff a0(y-x)=0 mod n0 iff y-x=kn0 (gcd(a0, n0)=1). So y=x0+kn0=x0+kn/d. That is: y is of the form we had already stablished.

We have proved the Uniqueness.

[r.maelstrom]

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.

[johns.]

Isn't this problem related to the cyclic group Z(n)?

[PunmasterSTP]

Linear congruences? More like "Liking this; cool it is!" 👍

[r.maelstrom]

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!

[krisbrandenberger]

@ 11:03 Should be k*x-l*y not l*y-k*x.

[Alan-zftt]

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 ∀ )