QR28 Magic of Numbers Joe Harris 11/27/02 Roots (mod n) and Computing Phi(n) Table of Contents ----------------------------------------------------------- I........ Review of finding roots (mod p) and (mod n). II....... Leads up to explanation of how/why our new recipe for computing Phi(n) will work. III, IV.. Recipe for computing Phi(n) -- step-by-step instructions. V........ Using Phi(n) to compute roots -- step-by-step instructions. ------------------------------------------------------------ I. Review of Previous Lecture. Prime Modulus p --------------- Fermat: If p is prime, and gcd(a,p)=1, (i.e. a /= 0 (mod p) ) then a^(p-1) == 1 (mod p). Roots (mod p): To find kth-root(a) (mod p), use Fermat to express "a" as a power of itself. a^1 == a^(1+p-1) == a^(1+2(p-1)) == a^(1+3(p-1)) ==... (mod p). Among these, find an exponent mk = 1 + l(p-1) divisible by k. Then (a^m)^k == a^(1+l(p-1)) == a (mod p), so a^m == kth-root(a) (mod p). Composite Modulus n ------------------- Euler: If n is prime OR composite, and gcd(a,n) = 1, then a^phi(n) == 1 (mod n). Roots (mod n): To find kth-root(a) (mod n), follow same procedure as in the (mod p) case, but substitute "(mod n)" for "(mod p)" and "phi(n)" for "p-1". Thus all we need now is a way to compute phi(n). ---------------------- II. Computing Phi(n) --- Example Attempts at Solution Definition: ----------- Phi(n) = number of numbers in modular arithmetic (mod n) relatively prime to n = number of numbers "a" between 0 and n-1 with gcd(a,n) = 1. Example Problem: Find phi(21). ---------------- Solution: --------- 1) Write down all the numbers between 0 and 20. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2) Cross out numbers NOT relatively prime to 21. = numbers "a" with gcd(a,21) > 1 = numbers divisible by 3, 7, or 21. = numbers divisible by 3 or 7 (since includes "21" case). - 1 2 - 4 5 - - 8 - 10 11 - 13 - - 16 17 - 19 20 3) Count how many numbers are left: Phi(n) = 12. Remark: The above solution is inefficient for large n! ------- For a large number n, we don't want to actually write down all the numbers between 0 and n-1, because that would take too long. Instead, we just _imagine_ that we have written down such a list and crossed off the numbers sharing prime factors with n, and then we "count without counting" to figure out how many numbers would be left if we had actually written them out. Improved Solution: Inclusion-Exclusion ----------------------------------------- Let's use inclusion-exclusion to "count without counting" how many numbers should remain in the list we constructed above to compute phi(21). Phi(n) = #{nums between 0 and 21 relatively prime to 21} Phi(n) = #{nums between 0 and 21} - #{nums divisible by 3 or 7} = 21 - [#{nums div by 3} + #{nums div by 7} - #{nums div by both}] = 21 - [ 21/3 + 21/7 - 21/21 ] = 21 - [ 7 + 3 - 1 ] Phi(n) = 12 Good! We got the same answer. Remark: This improved solution is awkward when n has many factors! ------- Suppose n = 1386 = 2 x 3^2 x 7 x 11. Then inclusion-exclusion becomes very complicated. For short-hand, write "ndb(2)" for "numbers divisible by 2," between 0 and 1385. Then using inclusion-exclusion, the full answer would be Phi(1386) = 1386 - [ ndb(2) + ndb(3) + ndb(7) + ndb(11) - ndb(2 and 3) - ndb(2 and 7) - ndb(2 and 11) - ndb(3 and 7) - ndb(3 and 11) - ndb(7 and 11) + ndb(2 and 3 and 7) + ndb(2 and 3 and 11) + ndb(2 and 7 and 11) + ndb(3 and 7 and 11) - ndb(2 and 3 and 7 and 11) ]. Scary! Fortunately, there is a simpler way to do this, if we think about crossing off numbers one at a time, and considering the _fraction_ of numbers still remaining. ----------------- III. Computing Phi(n) --- An even-better example solution. Inclusion-exclusion can get complicated, but there is a way out: whenever we cross of the numbers divisible by p from the list (for some new prime p whose multiples we have not yet crossed off), WE CROSS 1/P OF THE NUMBERS OFF LIST, AND LEAVE (P-1)/P REMAINING. For example, when we crossd of the numbers between 0 and 21 divisible by 3, we killed 1/3 of them (0, 3, 6, 9, 12, 15, 18) and left 2/3 remaining. Example Solution: ---------------- Phi(1386) = ? given that 1386 = 2 x 3^2 x 7 x 11. 0) Write #'s 0, ..., 1385 --> leaves 1386 numbers. 1 1) Cross off #'s divisible by 2 --> leaves 1386 x -. (kills 1/2 of the numbers) 2 1 2 2) Cross off #'s divisible by 3 --> leaves 1386 x - x -. (kills 1/3 of the numbers) 2 3 1 2 6 3) Cross off #'s divisible by 7 --> leaves 1386 x - x - x -. (kills 1/3 of the numbers) 2 3 7 1 2 6 10 3) Cross off #'s divisible by 7 --> leaves 1386 x - x - x - x --. (kills 1/3 of the numbers) 2 3 7 11 1 2 6 10 We're finished! Phi(1386) = 1386 x - x - x - x -- = 360. 2 3 7 11 --- ---------------- IV. Computing Phi(n) --- The General Recipe. Recipe for General Solution: --------------------------- 1) Find the prime factorization of n. 2) Make a list of the distinct primes dividing n. 3) Start with n, and for each distinct prime p dividing n, multiply by (p-1)/p. Example #1: What is Phi(85)? ---------- 1) 85 = 5 x 17. 2) 5 , 17 are the distinct primes dividing 85. 4 16 3) Phi(85) = 85 x - x -- = 64. 5 17 -- Example #2: What is Phi(48)? ---------- 1) 48 = 2^4 x 3. 2) 2, 3 are the distinct primes dividing 48. 1 2 3) Phi(48) = 48 x - x - = 16. 2 3 -- Example #3: What is Phi(p) when p is prime? ---------- 1) p = p. 2) p is the one prime dividing p. p-1 3) Phi(p) = p x --- = p-1, the same as what Fermat tells us. p ------------------------ V. Finding Roots (mod n) -- General Method. Problem: Find kth-root(a) (mod n). -------- Solution: --------- 1) Find Phi(n) using recipe from IV. 2) Use Euler's Theorem to express "a" as powers of itself: 1 + phi(n) 1 + 2(phi(n)) 1 + 3(phi(n)) a == a^ == a^ == a^ ==...(mod n). 3) Find an exponent among these that is divisible by k. i.e. Solve the equation mk = 1 + l(phi(n)) for m (and l). Or equivalently, solve mk == 1 (mod phi(n)) for m. 1 + l(phi(n)) mk k 4) Write a == a^ == a^ == (a^m)^ (mod n). Thus a^m == kth-root(a) (mod n). 5) Evaluate a^m (mod n). This answer is the kth-root of a. Example: What is 5th-root(3) (mod 85)? -------- 4 16 1) Phi(85) = 85 x - x -- = 64. 5 17 2) Euler says 3 == 3^65 == 3^129 == ... (mod 85). 3) 65 is divisible 5. 65 = 13x5. 4) 3 == 3^65 == (3^13)^5 (mod 85), so 3^13 == 5th-root(3) (mod 85). 5) 5th-root(3) == 3^13 == 63 (mod 85). --