Ah, welcome back my vigilant peons. Today we will be continuing the topic of our last discussion: modular arithmetic. Throughout this discussion, we will assume all numbers are integers.<\/p>\n
2. Euler’s Φ Function<\/span> Euler’s Phi<\/strong> (pronounced "fee<\/em>") Function Φ(n)<\/strong> is the count of the positive integers less than n that are relatively prime<\/em> to n. “Wait,” I hear you say, in a pathetically clueless tone, “what does it mean for two numbers to be relatively prime?” Well, my young padawan, if you’ll recall from 4th grade mathematics, two numbers are relatively prime if their greatest common divisor (GCD) is 1 – however, even if you don’t remember this, it’s not terribly important. Just know that if the larger of the two numbers is prime, then they will always be relatively prime to one another.<\/p>\n Here’s a quick quiz – if n is prime, what is Φ(n)? Here’s the point of all this – Euler discovered a neat little formula (aptly named Euler’s Formula<\/strong>) which says that, if a and n are relatively prime (there’s that word again!), then Let’s put our new theorem to use: say we want to find the value of 3123<\/sup> (mod 77)<\/span>. We note that 77 is the product of two primes; thus, Notice carefully what we did there. We realized by Euler’s Formula that 3Φ(77)<\/sup> ≡ 1 (mod 77)<\/span>, so we were able to keep taking out 360<\/sup><\/span> from 3123<\/sup><\/span> until we couldn’t take it out anymore. That is, we converted 3123<\/sup><\/span> to 3123 mod Φ(77)<\/sup><\/span> without changing its value (mod 77). It’s not hard to convince yourself that this is true in general; that is, if we’re trying to find the value of ak<\/sup> (mod n)<\/span>, then As we will see next post, it is this final formula that allows us to encrypt and decrypt messages in RSA encryption.<\/p>\n
\nIf you’ll recall, the last fun-filled example we gave was to find the last digit of 3403<\/sup><\/span> – we did this simply by noting that 34<\/sup> ≡ 1 (mod 10)<\/span> and following some simple logic. Today we generalize this technique.<\/p>\n
\nIf you’re wracking your brain for this one, then you’re not listening carefully enough. I just told you that if n is prime, then all positive integers less than it are relatively prime to it; since there are n-1 integers less than n,
\nΦ(n) = n-1 (if n is prime)<\/span>.
\nAlthough the general formula<\/a> for Φ(n) isn’t important for our purposes, I will state (though I know I haven’t been the most trustworthy person in the past, you’re just going to have to take my word on this one) that if n is the product of two primes, say n=p*q<\/span> (p and q both primes), then Φ(n) = (p-1)(q-1)<\/span>.<\/p>\n
\naΦ(n)<\/sup> ≡ 1 (mod n)<\/span>
\nThe proof of this is fairly simple (in fact, if you know group theory, it consists of literally four words); however, since we’re all so new to this whole modular arithmetic thing anyways, and since we all know that these so-called “proofs<\/em>” should really only be handled by those lowly peasants of pure-mathematics<\/em> – high class folk like us are only interested in the blatent, ignorant facts – we won’t dirty our precious hands any more than we have to.<\/p>\n
\nΦ(77) = (7-1)(11-1) = 60<\/span>.
\nTherefore,
\n360<\/sup> ≡ 1 (mod 77)<\/span>, and
\n3123<\/sup> ≡ (360<\/sup>)2<\/sup> * 33<\/sup> ≡ (1)2<\/sup> * 27 ≡ 27 (mod 77)<\/span>.<\/p>\n
\nak<\/sup> ≡ ak mod Φ(n)<\/sup> (mod n)<\/span><\/p>\n