WHERE DO EXPONENTS LIVE? In Normal math, performing operations with exponents is fairly straight-forward. (In fact, one might say that the exponents live on a number line.) Normal math (for a^k with a>1) ----------- * Higher exponents mean higher numbers: 3^30 < 3^60 < 3^90 < 3^90000 ... * Multiplying numbers with the same base is the same as ADDING exponents (and gives a LARGER number): 3^10 x 3^24 = 3^34. * Raising numbers to successive powers is the same as MULTIPLYING exponents (and gives a LARGER number). (3^4)^5 = 3^(4x5) = 3^20. * Taking roots of numbers is the same as DIVIDING exponents (and gives a SMALLER number). 5th root of 3 is 3^(1/5) = 1.245730.... 4th root of 2^8 is (2^8)^(1/4) = 2^2. In modular arithmetic, we perform analogous operations with exponents, but since modular arithmetic is such a wacky world, the outcome is rather different. Modular arithmetic. (for a^k (mod p=prime), a>1) ------------------- * The size of a^k has nothing to do with the size of k. In fact, due to Fermat's Theorem, the numbers GO IN A CYCLE as the exponent increases. 3^30 == 3^60 == 3^90000 == 1 (mod 31), 3^31 == 3 (mod 31). * Multiplying numbers with the same base is the same as ADDING exponents (but the resulting exponent CYCLES around each time we pass a multiple of (p-1) = 30): 3^10 x 3^24 = 3^34 == 3^2 (mod 31). * Raising numbers to successive powers is the same as MULTIPLYING exponents, (but the resulting exponent CYCLES around each time we pass a multiple of (p-1) = 30). (3^7)^5 = 3^(7x5) = 3^35 == 3^5 (mod 31). * Taking roots of numbers is ALMOST the same as DIVIDING exponents, except that we MUST CYCLE the exponent around lots of times by adding multiples of (p-1)=30 until we reach a multiple of the root so that we can actually divide. 7th root of 3 is 3^(1/7) == (3^ 1)^(1/7) == (3^31)^(1/7) == (3^61)^(1/7) == (3^91)^(1/7) <-- do-able! == 3^(91/7) == 3^13 (mod 31). Note that we could also have written this as 3^(1/7) == 3^( 1/7) == 3^(31/7) == 3^(61/7) == 3^(91/7) <-- do-able! == 3^(13) (mod 31). MORAL OF THE STORY: ------------------- EXPONENTS IN MODULAR ARITHMETIC LIVE ON A CIRCLE, TOO! If you compare the way we add, multiply and divide exponents in the two above cases, you will see that The difference between exponents in ordinary math and exponents in modular arithmetic (mod p=prime) is exactly the same as The difference between normal numbers in ordinary math and normal numbers in modular arithmetic (mod p-1). !!!! See all the similarities? * In exponents, multiples of (p-1) are treated like zero (since 3^30 == 3^60 == 3^90 == 1 == 3^0 (mod 31) ). --- * As you add 1 to the exponent, the exponent goes from 0 to 1 to 2 to 3, all the way up to 29, and then starts over again at 0 once it reaches 30. * If you multiply exponents and then want to evaluate what answer you have, you first must simplify the exponent using Fermat's theorem, i.e., reduce the exponent (mod 30) to a number between 0 and 29. * In order to take an nth root, or _divide_ exponents by n, you must add the appropriate multiple of 30 to the exponent to make it divisible by n before you divide. In fact, this is more than an illusion: For p a PRIME number... ________________________________________________________ | | | When NUMBERS live in modular arithmetic (MOD P), | | | | their EXPONENTS live in modular arithmetic (MOD P-1).| |______________________________________________________| You can take the above statement absolutely literally. Thus any time your problem in modular arithmetic involves exponents, you are actually dealing with 2 MODULI at ONCE, MOD P for NUMBERS, and MOD P-1 for EXPONENTS. Be very, very careful, never to confuse the two. It will never be valid to treat EXPONENTS as if they lived in (mod p), or NUMBERS as if they lived in mod p-1. PREVIEW FOR LECTURES 11/25/02 and 11/27/02 ------------------------------------------- The above ideas will become even more important when we move on to the next subject: the exponents belonging to numbers (mod n) when n is COMPOSITE. When n is composite, we don't have a Fermat's theorem allowing us to treat multiples of n-1 in the exponent as if they were zero. However, we do have an analog of Fermat's Theorem. FERMAT: When p is prime, and gcd(a,p)=1, p-1 0 a^ == a^ == 1 (mod p), so exponents live in (mod p-1). EULER: When n is ANY positive number, and gcd(a,n)=1, phi(n) 0 a^ == a^ == 1 (mod n), so exponents live in (mod phi(n)). Phi(n), called "Euler's Phi function" is just the name we give to a number that plays the same role as p-1 for prime numbers. There is a systematic way of computing Phi(n) for each n, which we will soon learn. Any guesses on what Phi(10) is, based on Homework 18?