Number Theory

Prove that the system of linear congruences in one variable given by

x ≡ a₁ mod m₁

x ≡ a₂ mod m₂

. . .

x ≡ a_r mod m_r

is solvable if and only if (mi, mj) | ai –aj, for all i ≠ j. In this case, prove that the solution is unique modulo[m1, m2, … ,m_r].

Iff = If and only if, it is a biconditional logical connective between statements. I think of it as the question and the proof.

Congruent = exactly equal in size and shape. It is a statement about divisibility. can you turn, inverse, change the position of the form, without changing it's size & shape. Sometimes you see this written as "you could lay one shape on top of another" almost like finding that puzzel piece and fitting it into the puzzel exactly. Sometims you have to rotate it in your hands to see where it fits.

Khan Academy Congruent Shapes & Transformations https://www.khanacademy.org/math/basic-geo/basic-geo-transformations-congruence/congruent-similar/v/another-congruence-by-transformation-example

A Linear Congruence is a congruence of the form, and is said to be a Solution if it satisfies this linear congruence. Linear Congruences serve as an introduction to CRT the Chinese Remainder Theorem

I found a nice lecture on this from the University of Chicago – while the Professor used the variable a, and your Professor used the variable of b, can you see the similarities?

http://gauss.math.luc.edu/greicius/Math201/Fall2012/Lectures/ChineseRemainderThm.article.pdf

Theorem (Chinese Remainder Theorem)

Let m1, m2, . . . , mr be a collection of pairwise relatively prime integers.

Then the system of simultaneous congruences

x ≡ a₁ (mod m₁)

x ≡ a₂ (mod m₂)

. . .

x ≡ a_r (mod m_r)

has a unique solution modulo M = m₁m₂, · · · m_r,

for any given integers a₁, a₂, . . . , a_r.

Proof of CRT (Chinese Remainder Theorem)

Put M = m₁ · · · m_r and for each k = 1, 2, . . . , r

let M_k = M/m_k .

gcd = greatest common divisor

Then gcd(M_k, m_k) = 1 for all k.

Let y_k be an inverse of M_k modulo m_k, for each k.

Then by definition of inverse we have M_ky_k ≡ 1 (mod m_k).

Let x = a₁M₁y₁ + a₂M₂y₂ + · · · + a_rM_ry_r.

Then x is a simultaneous solution to all of the congruences.

Since the moduli m1, . . . , mr are pairwise relatively prime, any two simultaneous solutions to the system must be congruent modulo M. Thus the solution is a unique congruence class modulo M, and the value of x computed above is in that class. Notice that the proof is constructive! Not only does it tell us why the theorem is true, it also gives an explicit formula for the solution.

Chinese Remainder Theorem https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-quotient-remainder-theorem