Linear Congruences • Definition ○ A congruence of the form ax≡b (mod m), ○ where m is a positive integer, a and b are integers, and x is a variable ○ is called a linear congruence. ○ The solutions to a linear congruence ax≡b (mod m) are ○ all integers x that satisfy the congruence. • Definition ○ An integer ā such that āa≡1 (mod m) is said to be an inverse of a modulo m. • Example ○ 5 is an inverse of 3 modulo 7 since 5∙3=15≡1 (mod 7) • One method of solving linear congruences makes use of an inverse ā, if it exists. • Although we can not divide both sides of the congruence by a • we can multiply by ā to solve for x. Inverse of a modulo m • The following theorem guarantees that • an inverse of a modulo m exists whenever a and m are relatively prime. • Two integers a and b are relatively prime when gcd(a,b) = 1. • Theorem 1 ○ If a and m are relatively prime integers and m 1, then an inverse of a modulo m exists. ○ Furthermore, this inverse is unique modulo m. ○ So, there is a unique positive integer ā less than m that is an inverse of a modulo m ○ And every other inverse of a modulo m is congruent to ā modulo m • Proof ○ Since gcd(a,m) = 1 ○ By Theorem 6 of Section 4.3, there are integers s and t such that sa + tm = 1. ○ Hence, sa + tm ≡ 1 (mod m). ○ Since tm ≡ 0 (mod m), it follows that sa ≡ 1 (mod m) ○ Consequently, s is an inverse of a modulo m. ○ The uniqueness of the inverse is Exercise 7. Finding Inverses • The Euclidean algorithm and Bézout coefficients gives us • a systematic approaches to finding inverses. • Find an inverse of 3 modulo 7. ○ Because gcd(3,7) = 1, by Theorem 1, an inverse of 3 modulo 7 exists. ○ Using the Euclidian algorithm: 7 = 2∙3 + 1. ○ From this equation, we get −2∙3 + 1∙7 = 1 ○ and see that −2 and 1 are Bézout coefficients of 3 and 7. ○ Hence, −2 is an inverse of 3 modulo 7. ○ Also every integer congruent to −2 modulo 7 is an inverse of 3 modulo 7 ○ i.e., 5, −9, 12, etc. • Find an inverse of 101 modulo 42620. ○ First use the Euclidian algorithm to show that gcd(101,42620) = 1. § 42620 = 45∙101 + 75 § 101 = 1∙75 + 26 § 75 = 2∙26 + 23 § 26 = 1∙23 + 3 § 23 = 7∙3 + 2 § 3 = 1∙2 + 1 § 2 = 2∙1 ○ Working Backwards § 1 = 3 − 1 ∙ 2 § 1 = 3 − 1 ∙ (23 − 7∙3) = − 1 ∙ 23 + 8 ∙ 3 § 1 = −1 ∙ 23 + 8 ∙ (26 − 1 ∙ 23) = 8 ∙ 26 − 9 ∙ 23 § 1 = 8 ∙26 − 9 ∙ (75 − 2 ∙ 26)= 26 ∙ 26 − 9 ∙ 75 § 1 = 26 ∙ (101 − 1∙75) − 9 ∙75 = 26 ∙ 101 − 35 ∙ 75 § 1 = 26 ∙ 101 − 35 ∙ (42620 − 45 ∙ 101) = − 35 ∙ 42620 + 1601 ∙ 101 ○ Bézout coefficients : − 35 and 1601 ○ Therefore 1601 is an inverse of 101 modulo 42620 Using Inverses to Solve Congruences • We can solve the congruence ax≡b (mod m) by multiplying both sides by ā. • What are the solutions of the congruence 3x ≡ 4 (mod 7). ○ We found that −2 is an inverse of 3 modulo 7 (two slides back). ○ We multiply both sides of the congruence by −2 giving ○ −2 ∙ 3x ≡ −2 ∙ 4(mod 7). ○ Because −6 ≡ 1 (mod 7) and −8 ≡ 6 (mod 7) ○ It follows that if x is a solution, then x ≡ −8 ≡ 6 (mod 7) ○ We need to determine if every x with x ≡ 6 (mod 7) is a solution. ○ Assume that x ≡ 6 (mod 7). ○ By Theorem 5 of Section 4.1, it follows that 3x ≡ 3 ∙ 6 = 18 ≡ 4 (mod 7) ○ which shows that all such x satisfy the congruence. ○ The solutions are the integers x such that x ≡ 6 (mod 7) ○ Namely, 6,13,20… and −1, − 8, − 15, … The Chinese Remainder Theorem • In the first century, the Chinese mathematician Sun-Tsu asked: ○ There are certain things whose number is unknown. ○ When divided by 3, the remainder is 2 ○ When divided by 5, the remainder is 3 ○ When divided by 7, the remainder is 2. ○ What will be the number of things? • This puzzle can be translated into the solution of the system of congruences: ○ x ≡ 2 (mod 3) ○ x ≡ 3 (mod 5) ○ x ≡ 2 (mod 7) • Theorem 2: (The Chinese Remainder Theorem) ○ Let m_1,m_2,…,m_n be pairwise relatively prime positive integers greater than one ○ Let a_1,a_2,…,a_n be arbitrary integers. ○ Then the system § x ≡ a_1 (mod m_1) § x ≡ a_2 (mod m_2) § ⋮ § x ≡ a_n (mod m_n) ○ has a unique solution modulo m=m_1 m_2⋯m_n. ○ That is, there is a solution x with 0≤x m ○ and all other solutions are congruent modulo m to this solution. • Proof ○ We’ll show that a solution exists by describing a way to construct the solution. ○ Showing that the solution is unique modulo m is Exercise 30. • Algorithm ○ To construct a solution first let M_k=m/m_k for k=1,2,…,n and m=m_1 m_2,…,m_n ○ Since gcd(m_k,M_k) = 1, there is an integer y_k, an inverse of M_k modulo m_k, such that § M_k y_k≡1 (mod m_k ) ○ Form the sum § x=a_1 M_1 y_1+a_2 M_2 y_2+a_3 M_3 y_3 ○ Note that because M_j ≡ 0 (mod m_k) whenever j≠k ○ all terms except the kth term in this sum are congruent to 0 modulo m_k . ○ Because M_k y_k ≡ 1 (mod m_k), we see that x ≡ a_k M_K y_k ≡ a_k (mod m_k), for k = 1,2,…,n. ○ Hence, x is a simultaneous solution to the n congruences. § x ≡ a_1 (mod m_1) § x ≡ a_2 (mod m_2) § ⋮ § x ≡ a_n (mod m_n) • Example ○ Consider the 3 congruences from Sun-Tsu’s problem: § x ≡ 2 (mod 3) § x ≡ 3 (mod 5) § x ≡ 2 (mod 7) ○ Let § m = 3∙ 5 ∙ 7 = 105 § M_1=m/3=35 § M_2=m/5=21 § M_3=m/7=15 ○ We see that § y_1= 2 is an inverse of M_1 = 35 modulo 3 since 35 ∙ 2 ≡ 2 ∙ 2 ≡ 1 (mod 3) § y_2= 1 is an inverse of M_2 = 21 modulo 5 since 21 ≡ 1 (mod 5) § y_3= 1 is an inverse of M_3 = 15 modulo 7 since 15 ≡ 1 (mod 7) ○ Hence, § x=a_1 M_1 y_1+a_2 M_2 y_2+a_3 M_3 y_3 § = 2 ∙ 35 ∙ 2 + 3 ∙ 21 ∙ 1 + 2 ∙ 15 ∙ 1 = 233 ≡ 23 (mod 105) ○ We have shown that 23 is the smallest positive integer that is a simultaneous solution. • Back Substitution ○ We can also solve systems of linear congruences with pairwise relatively prime moduli ○ by rewriting a congruences as an equality using Theorem 4 in Section 4.1 ○ substituting the value for the variable into another congruence, ○ and continuing the process until we have worked through all the congruences. ○ This method is known as back substitution. • Example ○ Use the method of back substitution to find all integers x such that § x ≡ 1 (mod 5) § x ≡ 2 (mod 6) § x ≡ 3 (mod 7). ○ By Theorem 4, the first congruence can be rewritten as x = 5t +1, where t is an integer. ○ Substituting into the second congruence yields 5t +1 ≡ 2 (mod 6). ○ Solving this tells us that t ≡ 5 (mod 6). ○ Using Theorem 4 again gives t = 6u + 5 where u is an integer. ○ Substituting this back into x = 5t +1, gives x = 5(6u + 5) +1 = 30u + 26. ○ Inserting this into the third equation gives 30u + 26 ≡ 3 (mod 7). ○ Solving this congruence tells us that u ≡ 6 (mod 7). ○ By Theorem 4, u = 7v + 6, where v is an integer. ○ Substituting this expression for u into x = 30u + 26 ○ tells us that x = 30(7v + 6) + 26 = 210v + 206. ○ Translating this back into a congruence we find the solution x ≡ 206 (mod 210) Fermat’s Little Theorem • Theorem 3: (Fermat’s Little Theorem) ○ If p is prime and a is an integer not divisible by p, then a^(p−1) ≡ 1 (mod p) ○ Furthermore, for every integer a we have a^p ≡ a (mod p) • This is useful in computing the remainders modulo p of large powers of integers. • Find 7^222 mod 11. ○ By Fermat’s little theorem, we know that 7^10 ≡ 1 (mod 11) ○ and so (7^10 )^k ≡ 1 (mod 11), for every positive integer k ○ Therefore, 7^222 = 7(22×10+2)=(710 )22×72 ≡ 1^22×49 ≡ 5 (mod 11). ○ Hence, 7^222 mod 11 = 5. Pseudoprimes • By Fermat’s little theorem n 2 is prime, where ○ 2^(n−1) ≡ 1 (mod n). • But if this congruence holds, n may not be prime. • Composite integers n such that 2^(n−1) ≡ 1 (mod n) are called pseudoprimes to the base 2. • Example: The integer 341 is a pseudoprime to the base 2. ○ 341 = 11 ∙ 31 ○ 2^340 ≡ 1 (mod 341) (see in Exercise 37) ○ We can replace 2 by any integer b ≥ 2. • Definition ○ Let b be a positive integer. ○ If n is a composite integer, and b^(n−1) ≡ 1 (mod n) ○ then n is called a pseudoprime to the base b • Given a positive integer n, such that 2^(n−1) ≡ 1 (mod n): ○ If n does not satisfy the congruence, it is composite. ○ If n does satisfy the congruence, it is either prime or a pseudoprime to the base 2. • Doing similar tests with additional bases b, provides more evidence as to whether n is prime. • Among the positive integers not exceeding a positive real number x, compared to primes • there are relatively few pseudoprimes to the base b. • For example, among the positive integers less than 〖10〗^10 there are 455,052,512 primes • but only 14,884 pseudoprimes to the base 2 Primitive Roots • Definition ○ A primitive root modulo a prime p is an integer r in Zp such that ○ every nonzero element of Zp is a power of r • Example ○ Since every element of Z11 is a power of 2, 2 is a primitive root of 11. ○ Powers of 2 modulo 11 § 2^1=2 § 2^2=4 § 2^3=8 § 2^4=5 § 2^5=10 § 2^6=9 § 2^7=7 § 2^8=3 § 2^9=6 § 2^10=1 • Example ○ Since not all elements of Z11 are powers of 3, 3 is not a primitive root of 11. ○ Powers of 3 modulo 11 § 3^1=3 § 3^2=9 § 3^3=5 § 3^4=4 § 3^5=1 § and the pattern repeats for higher powers. • Important Fact ○ There is a primitive root modulo p for every prime number p Discrete Logarithms • Suppose p is prime and r is a primitive root modulo p. • If a is an integer between 1 and p −1, that is an element of Zp, • there is a unique exponent e such that r^e = a in Zp, that is, r^e mod p = a. • Definition ○ Suppose p is prime ○ r is a primitive root modulo p ○ and a is an integer between 1 and p −1, inclusive. ○ If r^3 mod p = a and 1 ≤ e ≤ p − 1 ○ We say that e is the discrete logarithm of a modulo p to the base r and we write log_ra=e • Example 1 ○ We write log_23=8 ○ Since the discrete logarithm of 3 modulo 11 to the base 2 is 8 as 28 = 3 modulo 11. • Example 2 ○ We write log_25=4 ○ since the discrete logarithm of 5 modulo 11 to the base 2 is 4 as 24 = 5 modulo 11. • There is no known polynomial time algorithm for computing the discrete logarithm • The problem plays a role in cryptography as will be discussed in Section 4.6.
