Not your every day A squared plus B squared: Euler’s Theorem

This is the first post in a series of pieces on the sweetest formulae you’ve never heard of. These will be a selection of my favorite theorems and their simplified proofs; particularly those that make your head tilt because, honestly, we never learned any of those as kids. Also because I have a ton of other articles which I feel aren’t researched enough and I keep telling myself I’ll finish them. But really because this is pretty cool and it’ll make you more worldy. See? I did you a favor. Don’t say I never did anything for you.

If you’re not one for reading about math, and prefer it played out in front of you like a comical cabaret, Numberphile is an awesome web-series featuring UK-based mathematicians (some of them real heavy-weights in the field, like my old Hungarian, body-building, body-odorful calculus professor would have put it) that skew more towards the theory of numbers–which happens to be the field from which we obtain the result of Euler’s Theorem. The cool thing is it looks like the most useless thing ever, except you rely on it every day, in multiple ways, without even realizing it. No exercises were left to the reader in the making of this piece. You’ll be rewarded with better jokes as the math trudges on.

The man…

Euler was one of the greats. If G.H. Hardy (also a number theorist) were a sports caster (he hated sports as far as I can tell), he’d probably make the analogy that Euler is to Gauss what Abdul-Jabbar is to Bryant. Hardy was a little humble-brag in his essay “A Mathematician’s Apology”, but he actually ranks mathematicians, including himself, against the greats. Like saying Kobe Bryant is a 0.85 on the Michael Jordan scale. I digress. Euler was like the Chuck Norris of mathematics. He’s not known for being the absolute best; he’s known for being the most hardcore. He wrote hundreds of articles, fathered a literal litter of kids, and even when he developed cataracts and lost his eyesight, he continued to kick mathematical ass until the day he died. If someone could divide by zero, it would have been him. Actually, that was Riemann–sort of. Whatever.

…the myth…

But what’s the big deal about this theorem? Consider a salad bar. No. Consider a taco bar. All the ingredients are displayed before you: you got your tomatoes, cheese, sour cream, salsa, you name it. Now imagine all possible taco bars. Some taco bars might have guacamole, while others may have jalapeno, and still others fudge (desert tacos?). Euler’s Theorem is like a guarantee that no matter how ingredients are arranged, and regardless of how many you have, you’re always going to have a delicious taco. I suppose to the trained reader, this is a terrible analogy (I just needed some pulp for “the myth” part), but the truth of taco construction is irrefutable and important beyond consequence; if tacos couldn’t exist in near infinitude of combinations (the power set of taco ingredients, to be precise) and still be delicious, what would be the point of their existence? The taco would be robbed of it’s very taco quintessence. Uncountable tacos.

…the legend.

But real talk. This is Euler’s Theorem: if gcd(a, n) = 1 then a^{ \phi(n) } \equiv \, 1 \,\, mod(n).

MFW presented with math.

MFW presented with math.

If I’m reaching my intended audience, you’re like, “wat, it’s all Greek to me.” Basically it says, if the greatest common divisor of a and n is 1 (a doesn’t divide n and vice versa), then a raised to a special power, divided by n, will always have 1 left over as a remainder. To understand this theorem and its proof, you only need to know two things: modular arithmetic and relative primality. They sound complicated, but you do the former every day and the latter just sounds highfalutin.

Modular arithmetic simply refers to what’s left over after dividing: 5 modulo 3 is 2. 15 modulo 7 is 1. 6 modulo 3 is 0. It turns out it’s pretty handy when working with big numbers since the remainder adds, subtracts, multiplies, and divides just as easily as the numbers being divided themselves. Modular arithmetic was the pits when I first learned it since I promptly forgot how to multiply and divide when they gave us calculators in high school, but it’s pretty simple given the example people use every day: the 12 hour clock versus the 24 hour clock.

The 24 hour clock works by counting hours all the way up to 24, where we know that 0300 means 3:00 AM and 1500 means 3:00 PM.  Well, 3:00 PM is 15 modulo 12. 12 fits inside 15 once with 3 leftover, and we arrive at 3:00 PM.

Relative primality on the other hand is simply a question of whether or not one number divides another. Does 3 divide 8? No. 3 and 8 are relatively prime. Does 4 divide 8? Yes. 4 and 8 are not relatively prime. To be more exact, two numbers are relatively prime if their greatest common divisor is 1. Now, to save time, Euler came up with this thing he called the totient function: \phi(n). The function counts the number of numbers, less than the number n, that are relatively prime to the number n. Sounds convoluted, but easy enough: the totient of 5, for example, is 4. The numbers 1, 2, 3, and 4 are relatively prime to 5, and there are 4 numbers, less than 5, that are relatively prime to 5. How about 6? 1, 4, 5 are the only numbers less than 6 that are relatively prime to 6 (both 2 and 3 divide 6). So the totient of 6 is 3. A nice little fact is that the totient of a prime number (like 5), is one less than the number. Pierre “amateur hour” de Fermat noticed this. We’ll get to that later.

That’s all you need.

Proof

Shia LeBeouf SNL skit where he wiggles his fingers and says

This one’s for you, Dr. Wang

Lets try something assuming I math correctly. We’ll count by 3’s and see what the counting by 3’s looks like modulo 5.

3 \times 1 \equiv 3 \, mod(5)
3 \times 2 \equiv 1 \, mod(5)
3 \times 3 \equiv 4 \, mod(5)
3 \times 4 \equiv 2 \, mod(5)

3 \times 7 \equiv 21 \equiv 1 \, mod(5)
3 \times 8 \equiv 24 \equiv 4 \, mod(5)
3 \times 9 \equiv 27 \equiv 2 \, mod(5)

Notice that the remainders are just counting to 5. If we counted by 4 or 7 the remainders would just be rearranged and repeat itself every 4 steps. The important thing to note is that you’re guaranteed to have a complete shuffling of all 4 numbers, 1, 2, 3, and 4 every 4 steps. It’ll never skip. If we take the first 4 and multiply them together, we get:

3^{4} (1 \times 2 \times 3 \times 4) \equiv (1 \times 2 \times 3 \times 4) \, mod(5)

and dividing both sides:

3^{4} \equiv 1 \, mod(5)

As long as I choose the modulus (5 in this case) to be a prime number, say p, I can use any number less than p, call it a, and I’ll always have that:

a^{p-1} \equiv 1 \, mod(p)

This is called Fermat’s Little Theorem. It means that I can say that 50 raised to the power of 100, divided by 101, will have 1 left over. 50 to the 100th power has 169 digits. It’s a humongous number. But I didn’t have to do any multiplication to know a little something about how the prime number 101 will interact with other numbers less than it.

The requirement that the modulus p is a prime number is pretty restrictive, though. Prime number get pretty far apart pretty fast even though there are a whole bunch of fancy pairings of primes. I want to be able to do this with any modulus n that isn’t necessarily primeWell, this is where Fermat got put on the bench and Euler stepped in. Following along the lines of the proof of Fermat’s Little Theorem, we notice that for a modulus like 4, counting by threes looks like:

3 \times 1 \equiv 3 \, mod(4)
3 \times 2 \equiv 2 \, mod(4)
3 \times 3 \equiv 1 \, mod(4)
3 \times 4 \equiv 0 \, mod(4)
3 \times 5 \equiv 3 \, mod(4)
3 \times 6 \equiv 2 \, mod(4)
3 \times 7 \equiv 1 \, mod(4)
3 \times 8 \equiv 0 \, mod(4)

Because 4 isn’t prime, a pesky 0 shows up (3 times 4 divided by 4 leaves no remainder) but we see the same pattern of counting over and over, every 4 steps. But if we just toss out the remainders that aren’t relatively prime to 4, (remember, the totient of 4), we’re left over with just 1 and 3 since 2 divides 4. There are 2 remainders that don’t divide 4 also meaning that the totient of 4 is 2. Using the same idea as Fermat’s Little Theorem:

3^{\phi(4)} \equiv 3^2 \equiv 8 \equiv 1 \, mod(4)

The complete proof requires just a tiny bit of extra work, but in tossing out the remainders that divide 4, we recover what’s called a reduced residue system. The size of that set of number is the totient of the modulus.

Are you left with a complete sense of underwhelment?

The automotive embodiment of underwhelment.

The automotive embodiment of underwhelment.

Well, with this I can do even bigger math than in the previous example even faster in my head. But you must be thinking, Chase… who cares?

You do.

    …at least those of you who have ever bought anything with a credit card. And those of you reading this on a computer. It’s not so much about how Euler made mental math just a little bit easier, but how about Euler figured out a way for us to use big prime numbers like keys. These formulas form the foundation of the RSA algorithm.

RSA (and more grown up versions of it) is used everywhere. Buying an after-market spoiler for your beat up Honda Del Sol on Amazon cuz you want to impress women with questionable taste in men? RSA. Long story short, if you give me a big giant number, and we both know some big giant number relatively prime to it… do some multiplication and, bam, 1 left over, no matter what. A giant, glaring confirmation that we are both exchanging the correct information.

But here come the nay sayers. Here come the “what a gross oversimplification” critics. Worst of all, here come the people who say RSA is mostly broken–and totally broken when quantum computers hit the market. Well, even after the we enter the Willy Wonka’s Chocolate Factory of quantum computing where magical crap actually happens, lots of devices will still rely on classical transistors for the foreseeable future.  It’s not exactly cheap or easy to trap a qubit. See, we use Euler’s theorem in hash tables and maps–long story short, big prime numbers make it really easy for a computer to look things up in a table without having to search the entire table much in the same way that we can use them to act like a key.  It’s like when you get the corner piece of a puzzle there’s only four places it could possibly go, even though there are probably a thousand places total. Can you imagine watching someone check the middle of the puzzle with a corner piece in between their fingers?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s