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,

3

Tagged #modular-arithmetic, #math.

Similar posts

More by Jim

Want to build a fantastic product using LLMs? I work at Granola where we're building the future IDE for knowledge work. Come and work with us! Read more or get in touch!

This page copyright James Fisher 2017. Content is not associated with my employer. Found an error? Edit this page.