Season 9 Episode 6
In this episode, we learn about modular arithmetic with Beth, and apply it to send secret messages.
Further Reading
Modular Arithmetic
My definition for \(a\equiv b \mod n \) is “\(a-b\) is a multiple of \(n\)”. I sometimes pronounce that as “\(a\) and \(b\) are the same up to a multiple of \(n\)”. To clarify my definition, I also need to explain what I mean by “a multiple of”! My definition of “\(x\) is a multiple of \(y\)” is “there exists an integer \(k\) such that \(x=ky\)”! And finally, my definition of "integer” includes \(0\) and negative whole numbers, as well as positive whole numbers. Definitions within definitions!
Working backwards, that means that I have no problem with writing things like
\( 5\equiv 17 \mod 4,\qquad 17\equiv -7 \mod 4, \qquad -7\equiv -7 \mod 4 \)
That's because, in each case, the difference between the things on each side of the equivalence sign is a multiple of 4 (including negative multiples of 4, and the zero multiple of 4).
Lagrange’s Theorem
I’d like to explain why \(a^{p-1} \equiv 1 \mod p\) for any prime \(p\) and any integer \(a\) that’s coprime to \(p\). Actually, I can do a bit better, and link you to some content about Lagrange’s theorem.
There are some online lecture notes about group theory here from UCL (University College London); Chapter 4 Group theory | MATH0007. Lagrange’s theorem is proved in section 4.6, but I’m linking to the start of section 4 so that you can follow along with the definition of a group. Just like we saw in the discussion of modular arithmetic above, it’s good to start with the definitions, so that you understand what all the words mean later on!
Fermat’s Little Theorem says that \( a^{p-1} \equiv 1 \mod p\) for any prime \(p\) and any integer \(a\) that’s coprime to \(p\).
Once we've got Lagrange's Theorem, we can prove Fermat’s Little Theorem just by interpreting Lagrange’s Theorem for the special case of a particular group (the group of numbers from \(1\) to \(p-1\) with the operation “multiply modulo \(p\)”.
This is a common theme in mathematics; layers of abstraction and generalisation, each of which allows you to understand previous knowledge as a "special case" in some wider context.
There are also proofs of Fermat’s Little Theorem that don’t use Lagrange’s Theorem; for example, see OOMC Season 7 Episode 0 from last year, where Jonah proved FLT by counting bracelets, or for a proof by induction see Wolfram Mathworld (just before equation (4) on that page).
In the live episode, Beth also showed us an extended version of Fermat’s Little Theorem; if \(p\) and \(q\) are prime, and if \(a\) is coprime to \(pq\), then \(a^{(p-1)(q-1)}\equiv 1 \mod pq\).
This is also a special case of Lagrange’s Theorem, for the group where the elements are vectors \( (x,y) \) with \( 0\leq x \leq p-1\) and \(0\leq y \leq q-1\) and the group operation is “multiply component-wise, modulo \(p\) on the first component and modulo \(q\) on the second component”, together with the knowledge that if something is \( 1 \mod p \) and \(1 \mod q\) then it’s also \(1 \mod pq\). People sometimes invoke the Chinese Remainder Theorem to prove that last step, but I think it’s reasonably clear even if you don’t know what that is. And here’s a link to an NRICH article if you don't know what that is, but would like to.
Beth’s challenges
Beth has some more challenges for you;
- What’s the remainder when I divide \(25^{2025}\) by \(7\)?
- Describe all integers \(x\) such that \(3x\equiv 2 \mod 17\)
- What’s the last digit of \(777^{777}\)?
- What’s the remainder when \(4^{731}\) is divided by 7?
- What’s the remainder when \(1023^{1023}\) is divided by 5? What’s the last digit of \(1023^{1023}\)?
You can find more like this on Beth’s YouTube channel Maths Unboxed ("aesthetic mathsy videos, from GCSE to A Level help videos to insights into cool areas of university maths").
RSA
There’s a step-by-step guide for RSA cryptography at Cryptool here. They’ve picked the same primes as me! Oh rats, now you know my primes.
When we did this on the stream, you might have seen that Beth and I have a pre-arranged list of messages so that we can convert numerical messages into sentences easily. This is susceptible to attack, because if you think that Beth might be sending one of those five messages, then it’s not too hard for you to encrypt all of them and then simply compare the encrypted text to the message that Beth’s sending.
This sort of attack, where you know or guess all or part of the message, is relevant for actual codebreaking (for example, if you intercept the enemy’s weather reports, and they have a predictable format, then you can use that information). You can read more in any account of World War II codebreaking, of which there are many, but I’ll select Simon Singh’s Code Book as one example of such a book!
For more modern cryptography, you could try this primer on elliptic curve cryptography from the Cloudflare blog. Cloudflare are the company with a wall of lava lamps for generating random numbers, which you might have seen in, for example, this Tom Scott video: The Lava Lamps That Help Keep The Internet Secure | YouTube. That's probably a better idea than selecting the two smallest two-digit primes.
Jane Street Puzzles
If you liked the Jane Street puzzles we looked at a few weeks ago, they’ve posted a new one. This one has no instructions, just a cryptic combination of words and numbers. Good luck!
If you want to get in touch with us about any of the mathematics in the video or the further reading, feel free to email us on oomc [at] maths.ox.ac.uk.