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 ab ≡ ba, 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,
More by Jim
- A probabilistic pub quiz for nerds
- Time is running out to catch COVID-19
- The inception bar: a new phishing method
- The hacker hype cycle
- Project C-43: the lost origins of asymmetric crypto
- How Hacker News stays interesting
- My parents are Flat-Earthers
- The dots do matter: how to scam a Gmail user
- The sorry state of OpenSSL usability
- I hate telephones
- The Three Ts of Time, Thought and Typing: measuring cost on the web
- Granddad died today
- Your syntax highlighter is wrong
Tagged . All content copyright James Fisher 2017. This post is not associated with my employer. Found an error? Edit this page.