QR28 Magic of Numbers Dick Gross 11/25/02 Finding Roots (mod n) I. Finding Roots (mod p = prime) Problem: Given a (mod p) relatively prime to p, Find b = kth-root(a) (mod p), where gcd(k,p-1) = 1. Solution: Find a solution m to mk = 1 + l(p-1). [Or equivalently, mk == 1 (mod p-1). Then take b == a^m (mod p) for your answer. You can calculate a^m (mod p) by successive squaring. The solution works because b^k == (a^m)^k = a^(mk) = a^(1 + l(p-1)) = a^1 = a (mod p), so b^k == a (mod p), which means that b is the kth root of a. Remark: Note that there are TWO pairs of numbers that we need to be relatively prime: gcd(a,p) = 1 AND gcd(k,p-1) = 1. In particular, THIS METHOD WON'T WORK FOR FINDING SQUARE ROOTS, because p-1 is even for any prime number p > 2, and so gcd(k=2, p-1) = 2, NOT 1. Example. -------- Problem: Find 3rd-root(5) == ? (mod 17). Solution: 1) First check that numbers that need to be relatively prime are in fact relatively prime. * gcd(a = 5, p = 17) = 1. Good. * gcd(k = 3, p-1 = 16) = 1. Good. 2) Now apply Euclidean Alg to solve 3m == 1 (mod 16) for m. Solution: 3(11) - 16(2) = 1, so 3(11) == 1 (mod 16), so m == 11 (mod 16). 3) Now use successive squaring to find b == 5^11 (mod 17). 5^1 == 5 == 5 (mod 17) 5^2 == 25 == 8 (mod 17) 5^4 == 64 == 13 (mod 17) 5^8 == 169 == 16 (== -1) (mod 17) Thus b == 5^1 x 5^2 x 5^8 == 5 x 8 x (-1) == -40 == 11 (mod 17), and so 11 == 3rd-root(5) (mod 17). -- 4) (Optional.) We can check the answer, to convince ourselves that it is correct. 11^3 == 1331 == 5 (mod 17). It works! -- ---------------------------------- II. Finding roots (mod n = COMPOSITE) Problem: Given a (mod n) relatively prime to n, Find b = kth-root(a) (mod n). Solution: ??? We want to be able to divide exponents by k. In our solution (mod p = PRIME), the key ingredient was FERMAT's THEOREM: a^(p-1) == 1 (mod p) when gcd(a, p) = 1. This allowed us to add and or subtract multiples of (p-1) to the exponent until we could divide by k in the exponent and still get an integer. In order to use a similar technique for (mod n = COMPOSITE), WE NEED AN ANALOG OF FERMAT's THEOREM FOR COMPOSITE NUMBERS. That is, we need a rule that says WANTED THEOREM: a^(something) == 1 (mod n) when gcd(a, n) = 1. Does such a rule exist? How do we find it? We could guess that "something" = n-1, but one simple counter example will show that this is wrong. For example, Try a = 2, n = 15 (composite). Then gcd(2, 15) = 1. a^(n-1) == 2^14 == 16384 == 4 (mod 15). 4 is not 1, so a^(n-1) does not give 1 (mod n) in general. Enough guessing! Let's try to understand what's going on by looking at a proof of why Fermat's Theorem actually works. --------------- III. Euler's proof of Fermat's Theorem The following ideas are due to Leonhard Euler, born 1636. [Euler is my hero! He was one of the most original mathematicians known to history, was certainly the most prolific mathematician known to history, and he accomplished this despite blindness in later life, and despite the fact that he postponed publishing much of his work in order to give credit to younger mathematicians he was helping out. He was also a man of great faith.] Lemma [i.e., a mini-theorem used to prove a bigger theorem.] ----- If x /= y (mod p), then ax /= ay (mod p) for any gcd(a,p) = 1. [I'm typing /= for "not congruent".] Using the Lemma to Prove Fermat's Theorem ----------------------------------------- We want to show that a^(p-1) == 1 (mod p) for gcd(a,p) = 1. Bizarrely, we can accomplish this by comparing the following two products (mod p): i) 1 x 2 x ... x (p-2) x (p-1) = (p-1)! (mod p) and ii) 1a x 2a x ... x (p-2)a x (p-1)a = (p-1)! x a^(p-1) (mod p) All of the p-1 terms in the first product are distinct (mod p), so all of the p-1 terms in the second product are distinct (mod p). Thus in each case, since there are p-1 distinct numbers (mod p), and there are only p-1 values (mod p) that are relatively prime to p, these p-1 terms must precisely coincide with the p-1 numbers less than p that are relatively prime to p. That means that THE TWO ABOVE PRODUCTS ARE CONGRUENT (MOD P), since the terms in the second product are the same as the terms in the first product, but rearranged in some way: (i) == (ii), so (p-1)! == (p-1)! x a^(p-1) (mod p). Then, since all the terms in the product (p-1)! = 1 x ... x (p-1) are relatively prime to p, we can divide both sides by (p-1)! to obtain 1 == a^(p-1) (mod p). Finished!!! ----------------------- IV. Euler's Proof of EULER's THEOREM (for composites) Now, let's try the same procedure for composite modulus.... Lemma ----- If x /= y (mod n = composite), then ax /= ay (mod n) for any gcd(a,n) = 1. [I'm typing /= for "not congruent".] Using the Lemma to show a^(something) == 1 (mod n) -------------------------------------------------- In the case of prime modulus, we multiplied together all the _nonzero_ numbers (mod p), multiplied each of these by a, and then divided by each of the _nonzero_ numbers at the final step. However, using NONZERO numbers (mod n), i.e. multiplying together 1, 2, ..., n-1 to get (n-1)!, would NOT GENERALIZE correctly, because we can't divide by all of 1, 2, ..., n-1 in the last step, since not all of them are relatively prime to n. Instead, the approprate description of 1,2, ... ,p-1 (mod p) that _does_ generalize appropriately is that these are the numbers RELATIVELY PRIME TO p. Let's apply that description for n. First, we form the product of the numbers less than n and RELATIVELY PRIME to n. (e.g. look at n=15:) i) prod1 = 1 x 2 x 4 x 7 x 8 x 11 x 13 x 14 (mod n = 15) Next, we form a new product by multiplying each of these numbers by any number a with gcd(a,n) = 1: ii) prod2 = 1a x 2a x 3a x 4a x 8a x 11a x 13a x 14a (mod 15) == a^8 x (1 x 2 x 4 x 7 x 8 x 11 x 13 x 14) (mod 15) prod2 == a^8 x prod1 (mod 15) Now, the numbers relatively prime to n forming the terms of prod1 (e.g. 1,2,4,7,8,11,13,14) are distinct (mod n), we by the Lemma, we know that terms in prod2 (e.g. 1a,2a,4a,7a,8a,11a,13a,14a) are also distinct (mod n). Moreover, since (a # rel prime to n) x (a # rel prime to n) = (a # rel prime to n), we know that all the terms in prod2 are relatively prime to n. Well, there are only 8 distinct numbers mod n that are relatively prime to n, and so, since there are 8 distinct terms in prod1, and 8 distinct terms in prod2, and all of these numbers are relatively prime to n, we know that these the terms in prod1 must be the same (mod n) as the terms in prod2 (though in a different order). Thus prod1 == prod2 prod1 == a^8 x prod1 (mod n = 15) Finally, since prod1 is relatively prime to n, we can divide both sides of the congruence by prod1, and obtain 1 == a^8 (mod n = 15) Finished!!!! --------------------- That's great! We've found that when n=15, the "something" we want for our analog of Fermat's theorem is not 15-1, but 8, so that a^8 == 1 (mod 15) when gcd(a,15) = 1, but where on earth did 8 come from, and how do we generalize? Remember: 8 was the number of terms in the product prod1, which was "the number of numbers less than n(=15) and relatively prime to 15". Thus we have our general answer: ____________________________________________________________ | | |EULER's THEOREM: | |---------------- | | If gcd(a,n) = 1, then | | | | a^ phi(n) == 1 (mod n), | | | | where "phi(n)" is short-hand for "The number of numbers | | between 1 and n, and relatively prime to n". | | | | | | This number phi(n) (written with the Greek symbol "phi") | | is called "Euler's Phi-function," or more simply, | | "Euler's number". | | | |__________________________________________________________| On Wednesday, Joe will talk about easy ways to compute phi(n) for random composite numbers n.