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.

2. Euler’s Φ Function

If you’ll recall, the last fun-filled example we gave was to find the last digit of 3^{403} – we did this simply by noting that 3^{4} ≡ 1 (mod 10) and following some simple logic. Today we generalize this technique.

**Euler’s Phi** (pronounced "*fee*") **Function Φ(n)** is the count of the positive integers less than n that are *relatively prime* 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.

Here’s a quick quiz – if n is prime, what is Φ(n)?

If 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-1 (if n is prime).

Although the general formula 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 (p and q both primes), then Φ(n) = (p-1)(q-1).

Here’s the point of all this – Euler discovered a neat little formula (aptly named **Euler’s Formula**) which says that, if a and n are relatively prime (there’s that word again!), then

a^{Φ(n)} ≡ 1 (mod n)

The 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*” should really only be handled by those lowly peasants of *pure-mathematics* – 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.

Let’s put our new theorem to use: say we want to find the value of 3^{123} (mod 77). We note that 77 is the product of two primes; thus,

Φ(77) = (7-1)(11-1) = 60.

Therefore,

3^{60} ≡ 1 (mod 77), and

3^{123} ≡ (3^{60})^{2} * 3^{3} ≡ (1)^{2} * 27 ≡ 27 (mod 77).

Notice carefully what we did there. We realized by Euler’s Formula that 3^{Φ(77)} ≡ 1 (mod 77), so we were able to keep taking out 3^{60} from 3^{123} until we couldn’t take it out anymore. That is, we converted 3^{123} to 3^{123 mod Φ(77)} 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 a^{k} (mod n), then

a^{k} ≡ a^{k mod Φ(n)} (mod n)

As we will see next post, it is this final formula that allows us to encrypt and decrypt messages in RSA encryption.

## One Comment

Tune in next week for the exciting conclusion – same bat-time, same bat-place!

## Trackbacks/Pingbacks