A brief note on Congruences and the Chinese Remainder Theorem . Read it before a test. Try each question at the end before you open its answer.
Congruences Meaning: a ≡ b ( m o d m ) a \equiv b \pmod m a ≡ b ( mod m ) when m ∣ a − b m \mid a - b m ∣ a − b , that is, the same remainder on division by m m m . Rules: add, subtract, multiply and take powers on both sides; any polynomial with integer coefficients keeps the congruence. Cancelling: from a c ≡ b c ( m o d m ) ac \equiv bc \pmod m a c ≡ b c ( mod m ) you get a ≡ b ( m o d m / gcd ( c , m ) ) a \equiv b \pmod{m/\gcd(c, m)} a ≡ b ( mod m / g cd( c , m )) . Large powers: find a small power a k ≡ ± 1 a^k \equiv \pm 1 a k ≡ ± 1 and cut the exponent by k k k . Squares: 0 0 0 or 1 1 1 modulo 4 4 4 ; 0 0 0 , 1 1 1 or 4 4 4 modulo 8 8 8 . Linear congruences Solvable: a x ≡ b ( m o d m ) ax \equiv b \pmod m a x ≡ b ( mod m ) exactly when d = gcd ( a , m ) d = \gcd(a, m) d = g cd( a , m ) divides b b b ; then d d d solutions modulo m m m . Method: divide a a a , b b b and m m m by d d d , then multiply by the inverse. Inverse: exists exactly when gcd ( a , m ) = 1 \gcd(a, m) = 1 g cd( a , m ) = 1 ; the extended Euclidean algorithm finds it. The Chinese remainder theorem Pairwise coprime moduli: exactly one solution modulo the product. Lifting: x = a 1 + m 1 t x = a_1 + m_1 t x = a 1 + m 1 t , then reduce modulo the next modulus. Shared factor: solvable when gcd ( m , n ) ∣ a − b \gcd(m, n) \mid a - b g cd( m , n ) ∣ a − b , unique modulo the lcm. Counting: the number of solutions modulo m 1 m 2 m_1 m_2 m 1 m 2 is the product of the counts. A worked example Find x x x with x ≡ 4 ( m o d 5 ) x \equiv 4 \pmod 5 x ≡ 4 ( mod 5 ) and x ≡ 5 ( m o d 9 ) x \equiv 5 \pmod 9 x ≡ 5 ( mod 9 ) .
Lift. x = 5 + 9 t x = 5 + 9t x = 5 + 9 t , and 5 + 9 t ≡ 4 ( m o d 5 ) 5 + 9t \equiv 4 \pmod 5 5 + 9 t ≡ 4 ( mod 5 ) gives 4 t ≡ 4 4t \equiv 4 4 t ≡ 4 , so t ≡ 1 t \equiv 1 t ≡ 1 . Answer. x = 14 x = 14 x = 14 , unique modulo 45 45 45 . Check. 14 = 2 × 5 + 4 = 9 + 5 14 = 2 \times 5 + 4 = 9 + 5 14 = 2 × 5 + 4 = 9 + 5 . Practice with new numbers
A program to try The program checks a power, an inverse and a small system.
Read it first. Then run it. Does each line agree with the rules above?
1. Change the system to x ≡ 2 ( m o d 6 ) x \equiv 2 \pmod 6 x ≡ 2 ( mod 6 ) and x ≡ 1 ( m o d 4 ) x \equiv 1 \pmod 4 x ≡ 1 ( mod 4 ) . Why is the list empty?
Mistakes to avoid Cancelling a factor that shares a factor with the modulus. Reducing an exponent modulo m m m . Only the base is reduced modulo m m m . One solution when there are gcd ( a , m ) \gcd(a, m) g cd( a , m ) of them. Using the theorem with moduli that share a factor without checking that the remainders agree. Check yourself Find the remainder of 2 100 2^{100} 2 100 on division by 11 11 11 . Stuck? Show a hint Show the answerSolve 7 x ≡ 1 ( m o d 26 ) 7x \equiv 1 \pmod{26} 7 x ≡ 1 ( mod 26 ) . Stuck? Show a hint Show the answerSolve x ≡ 1 ( m o d 4 ) x \equiv 1 \pmod 4 x ≡ 1 ( mod 4 ) and x ≡ 3 ( m o d 5 ) x \equiv 3 \pmod 5 x ≡ 3 ( mod 5 ) . Stuck? Show a hint Show the answerHow many solutions has 4 x ≡ 6 ( m o d 10 ) 4x \equiv 6 \pmod{10} 4 x ≡ 6 ( mod 10 ) from 0 0 0 to 9 9 9 ? Stuck? Show a hint Show the answerSources David M. Burton, Elementary Number Theory , Chapter 4, The Theory of Congruences.