Notes - Congruences

The following are notes from Introduction to Cryptography with Coding Theory.

• Modular Arithmetic or Congruences
• Let a, b, n be integers with n ≠ 0 
• a ≡ b (mod n) 
• read as a is congruent to b mod n if a-b is a mutliple of n
• or congruent if a and b differ by a multiple of n
• can be rewritten as a = b + nk for some integer k
• Examples
• 32 ≡ 7 mod 5
• -12 ≡ 37 mod 7
• Proposition
• let a, b, c, n be integers with n ≠ 0
• a ≡ 0 mod n if and only if n|a
• a ≡ a mod n 
• a ≡ b mod n
• if a ≡ b and b ≡ c mod n, then a ≡ c mod n
• Proposition
• let a, b, c, d, n be integers with n ≠ 0 and suppose a ≡ b mod n and c ≡ d mod n
• then a + c = b + d, a - c = b - d, ac ≡ bd mod n
• Modulo operations
• addition - we add them as integers then if the product is less than n we stop, if the product is larger than n-1 then we divide by n and take the remainder. 
• subtraction - same as addition
• multiplication- same as addition
• note -  we can use negative but usually use positive integers
• division
• let a, b, c, d, n be integers with n ≠ 0 and with gcd(a,n)=1. If ab ≡ ac mod n then b ≡ c mod n. In other words, if a and n are relatively prime,we can divide both sides of the congruence by a
• Examples
• Solve 2x + 7 ≡ 3 mod 17
• 2x ≡ -4
• x ≡ -2 ≡ 15
• division allowed because gcd(2,17) = 1
• Solve 5x + 6 ≡ 13 mod 11
• 5x ≡ 7
• 7 ≡ 18 ≡ 29 ≡ 40
• 5x ≡ 7 is equivalent to 5x ≡ 40
• x ≡ 8 mod 11
• Proposition
• Suppose gcd(a,n) = 1. Let s and t be integers such that as + nt = 1. (They can be found via the extended euclidean algorithm) Then as = 1 mod n, so s is the multiplicative inverse for a mod n
• Example
• solve 11,111x ≡ 4 mod 12,345
• gcd
• 12,345 = 1 * 11,111 + 1,234
• 11,111 = 9 * 1,234 + 5
• 1234 = 246 * 5 + 4
• 5 = 1 * 4 + 1
• 4 = 4 * 1 + 0
• Extended Euclidean Method
• x₀ = 0
• x₁ = 1
• x₂ = -1 * 1 + 0 = -1
• x₃ = -9 * -1 + 1 = 10
• x₄ = -246 * 10  + -1 = -2461
• x₅ = -1 * -2461  + 10 = 2471
• Therefore
• 11111 * 2471 + 12345 * y₅ = 1
• 11111 * 2471 ≡ 1 (mod 12345)
• multiple original 11111x ≡ 4 by 2471 to get
• x ≡ 9884 (mod 12345)
• Summary
• Finding a^-1 (mod n)
• use extended euclidean algorithm to find integers s and t such that as + nt = 1
• a^-1 ≡ s (mod n)
• Solving ax ≡ c (mod n) when gcd(a,n) = 1
• use the extended euclidean algorithm to find as + nt = 1
• the solution is x ≡ cs (mod n)
• What if gcd(a,n)>1?
• If d does not divide b, there is no solution
• assume d|b consider the new congruence
• (a/d)x ≡ b/d (mod n/d)
• solve above to obtain solution x₀
• the solutions of original congruence ax ≡ b (mod n)
• x_0, x₀ + (n/d), x₀ + 2(n/d),...., x₀+(d-1)(n/d) mod n
• Example
• solve 12x ≡ 21 (mod 39)
• gcd (12,39) =3
• divide by 3
• 4x ≡ 7 (mod 13)
• we can get a x₀ of 5 through trial and error or the extended euclidean method
• we get two more solutions by adding 39/3 once then twice to obtain 18 and 31 as other answers.

Back to ToC