zahlen alors!

Bonjour, madames et monsieurs! There's little cargo to be found on the medical update train, but it's making a stop regardless. Lather, rinse, repeat. I get nervous when I haven't had to venture to the hospital for a long time... The threat of what might happen next looms ominously over my weekly plans. So it goes, I suppose.

Well, I've obviously been hung up on some pretty severe I'm-not-a-writer's block for quite some time. Not much is happening, so most of what goes on in my microcosm is Extreme Nerd Mental Gymnastics(!) mind games. I have a fantastically giant, searingly blue digital clock in direct view 24/7, constantly burning new sextets into my retinas; who would I be if I weren't ignoring responsibilities staring into that azure tickerscape, racing to find patterns with every tick? notjlink, that's who.

Anyway, the plan was to talk about adding and multiplying clock numbers together - for example, multiplying hours * minutes and figuring out what the answer would look like in seconds - and then ramble about how it's just a restriction on "normal" math, finally drawing back the curtain to reveal the magic that is modular arithmetic. I even went so far as to write out a game and a follow-up explanation/tutorial/condescensionfest.

With all of that tappy-tapped out and nearly finalized, though, I hopped over to Wikipedia to make sure I had all of my modular ducks in a row (again, not beforehand like a real writer)... and saw that they had said it all better in about as much space as I've wasted whining in this post so far. Hmph! So on that note, I'm just going to point you to their page (no need to read more than the intro), and then we can dive into what I've really been pondering.



If you'd rather not venture away right now, let me quicksplain two things I'm going to use over and over, and then we can dig in:


1) The three-horizontal-bar symbol I'm going to spew all over (≡) is the congruency symbol. It means "the same as far as we're concerned", which is slightly different from the normal equals-sign. Think of drawing a 30-degree angle and a 390-degree angle: they look the same, but they're technically not equal. That's congruency.

2) I'm more or less going to restate this right away, but just for the record: when I say "(mod 100)", it means looking at a number and only paying attention to the last two digits. For example, 17 (mod 100) is still 17, while 117 (mod 100) is also the same as 17 as far as we're concerned. So, 117 ≡ 17 (mod 100). They're not equal, but they're interchangeable (mod 100), so we call them congruent. They're not necessarily interchangeable if we pick a different number besides 100, but I won't bother you with definitions right this second.


Beyond that, the actual math across the moat of terminology is not overwhelming. Speaking of vocab and typography, I'll try to be consistent, but I'm not exactly textbook-typesetting a blog rant here. Ready? Let's go!



Many moons ago, before memorization kicked in, I used to attempt to deal with anxiety by multiplying by two over and over again, but only paying attention to the last two digits of the product. That is, I would count 2, 4, 8, 16, 32, 64, 28 (not 128), 56 (28*2, not 128*2), 12 (not 112 or 512), and so on. This is pretty easy to do; it's only multiplying by two, and when a number gets bigger than 100, we can drop the extra digit. What this really is, is calculating the powers of two (mod 100) - but rather than doing it the computer way by solving 2^19 = 524288 ≡ 88 (mod 100), for example, we're doing it the human way by multiplying by two 19 times and reducing (mod 100) at every possible opportunity. Anyway, doing this multiplication is just easy enough, but also just distracting enough to be a [brief] anxiety repellent. When twos grow too easy/ineffective, switching to threes is a bit more difficult, but still the same theoretical and practical process. Multiplying threes (mod 100) also makes what I'm talking about a lot cleaner.

What's fun (and convenient, and helpful) about this mental ninjutsu is that it eventually repeats. As we chug along multiplying by three, for example, it starts 3, 9, 27, 81, (2)43, (1)29, 87, and so on. But eventually it comes around to [...], 63, (1)89, (2)67, (20)1, 3, 9, 27, and hey, we're back where we started. It's a 20-number sequence, which turns out to be significant, but that just means that the first number is the same as the 21st, the fifth is the same as the 25th, etc. To me, wrapping around to the beginning of the cycle means I've "won" - I did all of my mental math correctly and didn't get stuck on some other loop, which would mean I was sloppy somewhere in the middle.

Note that multiplying by two also loops in a 20-number cycle, with one caveat: starting with two, it goes 2, 4, 8, 16, ..., 44, 88, 76, 52, 4, 8, and on from there. So, instead of cycling back to two before four, it actually hits 52. Dr. Tiede would remind you that this makes the sequence ultimately periodic, and it's because two and 100 aren't relatively prime ("coprime"). irRegardlessly, it still does the same cyclical process aside from that initial starting point, hitting 52 before 4.

When we're just looking at the last two digits like this, it turns out that every single number loops after no more than 20 rounds. I'm not going to list them all, but remember that. We'll eventually figure out why.

It makes sense that this repeated multiplication would eventually cycle. If we're only looking at the last two digits, our only options are 0-99, and at most we could hit each of those numbers once before the cycle starts repeating. Hooray for the pigeonhole principle!

That's actually a certified Big Deal in modular arithmetic. It's a contortion of Fermat's little theorem, which [insert excessive details here] says that x^n ≡ x (mod n) as long as x and n are relatively prime. In our case of multiplying threes and keeping the last two digits, it translates to finding the number in the cycle that comes 100 positions after three. The theorem says it's three.

So do we. (Not just because Wolfram Alpha tells us 3^101 = 1546132562196033993109383389296863818106322566003, which ends with "03". Only counts if you calculated that in your head!) How so? Well, running all the way out from our starting position #1 (three) to position #101 is overkill. (Spoiler alert: it's because 100 isn't prime.) We already figured out that threes (mod 100) cycle after 20 rounds so since position #1 is a three, position #21 is also three. Twenty rounds later, position #41 will be three as well. Then it's the same for #61, #81, and #101. Ta-da! Fermat's a smart cookie, disregarding the fact that my pigeonhole-principle plausibility predication is more proof than he ever proffered. He tends to do that.


--------ASIDE----------------

At the risk of disrupting my tenuous continuity, let's see an easy example of Fermat's little theorem in full force: consider multiplying twos again, but (mod 5) this time. The first few numbers are again 2->4->8->16->32, which when converted (mod 5) is 2->4->3->1->2. So, 2^5 ≡ 2 (mod 5), as declared. In fact, here are the cycles for every possible case (mod 5):

0 -> 0 -> 0 -> 0 -> 0
1 -> 1 -> 1 -> 1 -> 1
2 -> 4 -> 3 -> 1 -> 2   (2->4->8->16->32)
3 -> 4 -> 2 -> 1 -> 3   (3->9->27->81->243)
4 -> 1 -> 4 -> 1 -> 4*  (4->16->64->256->1024)

*Note that 4 = 2^2, so its sequence is equivalent to taking the second, then fourth, then sixth, etc., items in the cycle of twos. Ergo, it traverses twice as fast and cycles in half as many steps.

That's every possible number (mod 5), so we've brute-forced a proof that the little theorem doesn't short-circuit when the modulus is prime. This is different from (mod 100), where every integer (mod 100) has a cycle of no more than 20. That part is a massively important difference. Now, back to the show!

-------/ASIDE----------------


Hey, look, casual mental math led us to derive a textbook-level whopper! We're as smart as Fermat then, right? ;-) Actually, we've unwittingly done him one (or even two) better. Ol' Pierre's little theorem is a strict limit if the modulus is prime. We've been running (mod 100) though, and 100 is quite not-prime. The maximum cycle is 20 rounds too, which is far fewer than Fermat insists. To get [closer] to that smaller cycle length, we have to be slick like Euler.

Let's go back to threes (mod 100), because it's so neat and tidy. There are 100 numbers that could hypothetically be in the cycle, anything 0-99. However, many of those numbers are unattainable. We can rule out all of the even numbers right away, as every power of three will be odd. That brings us down to 50 options. We can also ignore the odd multiples of five; because we're working (mod 100), we would need to multiply by five at some point to get a number ending in "5", but we're in love with three right now. There are 10 of those, so we've carved our way down to 40 options. Hmmm...

This is where Euler's theorem appears. Err, sort of - we got the same result of 40 options as his theorem would tell us, but we did it with a healthy dose of convenience and handwavium. And threes (mod 100) do repeat after 40 rounds; we already established that the first number is the same as the 21st number, and running through the cycle again produces the same number 20 more rounds later, for a total of 40 rounds. Euler takes us to that number by calculating the totient of 100, which is almost what we did. I'm not going to get into it too robustly, but the totient of a number x (written φ(x)) is the total count of numbers less than x that are relatively prime to x. (Sorry, vocab!) For prime numbers, φ(x) = x-1, because a prime number doesn't have any factors to share. In the offset demo above regarding (mod 5), φ(5) = 4, and the theorem says (in our twisted version) that the number at that point in the cycle should be a 1. Indeed, it goes 2->4->8->16, and 16 ≡ 1 (mod 5).

The totient of 100 is 40. You can use the rules for totients of composite numbers, but we're clinging onto the last thread of mental mathliness, so we're going to get there our (now familiar) way. The totient of a number is the count of smaller numbers with no shared factors, so we can eliminate the ones that do share factors, and then see what's left. Don't worry: 100 = 2*2*5*5, so we only have two (familiar!) factors. Since two is a factor, all of the evens are out - that takes us down to 50 possible coprimes; out of those, there are 10 odd multiples of five between 1-99, so those are out too. That gets us to 40 numbers less than 100 that don't share factors with 100. If you want to do that calculation constructively, rather than by elimination, consider that 1, 3, 7, 9, 11, 13, 17, 19, ... (the odds without the fives) are all relatively prime to 100. That's four out of every 10, which adds up to 40.

So there, we've caught up with Lenny-E! Alas, his limit on twos or threes (mod 100) is 40 rounds per cycle, but the biggest loop (mod 100) in just 20. That's right: we're about to one-up the guy awesome enough to have his own number.

...Sort of. This last jump is hard to make via simple mental math accident. It turns out we've stumbled across a number, 100, where the biggest cycle of exponentiation is actually half of the totient. (Note that I said "biggest": some numbers have shorter cycles. Fives get stuck on 25 after one iteration, and even crazy coprime seven loops back after just four rounds.) The Carmichael function (written λ(x), because Greek is awesome - but don't think it's anything fishy, stats people!), says that sometimes the maximum cycle length will be the totient, and sometimes it'll be half of the totient. Explaining when to expect which value is quite a mess to write out, so either take my word for it or go read the gory details!

Anyway, 100 is one of the half-totient numbers... which we (non-rigorously) figured out with quasi-easy mental math. We even did it the backwards way, starting with the most-refined final answer. Hooray!

Just to make sure we have it down, let's run through all of this quickly again using the most common purveyor of modular arithmetic on the planet: the clock. That is, let's follow the seconds-hand around, ignoring the effects on minutes and hours. It's (mod 60): the numbers go 0-59, and 60 is the same as zero. If we start multiplying twos together, we go 2->4->8->16->32->(6)4->8->... Since two is a factor of 60, we get the same small aberration as with 100 - on the fifth round we have 32, but on the sixth round it's back to four. Position #6 is the same as #2, position #7 is the same as position #3, etc., so the cycle is four rounds. More tidily, multiplying sevens goes 7->49->43->1->7->... (corresponding to the first few powers of seven: 7, 49, 343, 2401, ...) Again, the cycle is four rounds. That aligns with Fermat's claim that we should be back at the start after 60 rounds; since we're back after four, we'll be back after any multiple of four. Even better: the totient of 60 is merely eight (60 has a lot of factors), and if we do eight rounds of the cycle - two complete cycles - we're back at the start. To put a bow on it, the Carmichael function says 60 is one of those half-totient numbers, so our final cycle length is four. You can mentally verify this much easier than the (mod 100) case since it's such a short cycle, but it's much less satisfying.



We win! We even outdid two of the most brilliant math dudes in history and matched a third (ok, maybe that's a stretch), and we did it sans pencil/paper/calculator, in a distressed mental state. A+ for everyone.

So, uh, I guess that's it for now. I desperately need to stop proofreading and click "publish" already. Tune in next time for something you might actually enjoy reading! Q-E-sloppily-D.