Learn more about Russian war crimes in Ukraine.

Modular multiplication

How about multiplication? If you multiply n by 5 on a clock-face, is there an inverse which undoes this? Yes: multiply by 5 again! Try it: (4×5)×5 = 4 (mod 12). Try it again: (9×5)×5 = 9 (mod 12).

Why does this work? Consider that multiplying by 5 twice is multiplying by 25. Multiplying by 25 is an identity on the 12-hour clock-face: it does nothing. Similarly, multiplying by 7 undoes itself, because ×49 is an identity, and ×11 undoes itself, because ×121 is an identity.

1, 25, 49, 121 - all these numbers are ≡ 1 (mod 12). 25 = 2×12+1, 49 = 4×12+1, et cetera. So, ×a is the inverse of ×b if ab ≡ 1. Since abba, these inverses are paired up.

It’s coincidence that the inverses are squares for mod-12. For mod-10, ×3 and ×7 are inverses, because 3×7 ≡ 1 (mod 10).

If the modulus is pq, what inverses exist? For example, if p = 7 and q = 5,

i.e. if ab = kn + 1.

What numbers are congruent to 1 in mod-12? 1, 13, 25, 37,


What can computers do? What are the limits of mathematics? And just how busy can a busy beaver be? This year, I’m writing Busy Beavers, a unique interactive book on computability theory. You and I will take a practical and modern approach to answering these questions — or at least learning why some questions are unanswerable!

It’s only $19, and you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

After months of secret toil, I and Andrew Carr released Everyday Data Science, a unique interactive online course! You’ll make the perfect glass of lemonade using Thompson sampling. You’ll lose weight with differential equations. And you might just qualify for the Olympics with a bit of statistics!

It’s $29, but you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

More by Jim

Tagged . All content copyright James Fisher 2017. This post is not associated with my employer. Found an error? Edit this page.