Dividing in clock arithmetic
Tonight's idea
On a clock with \(m\) hours you keep only the remainder after dividing by \(m\). We write \(x \equiv y \pmod m\) when \(x\) and \(y\) leave the same remainder. Adding and multiplying are easy. Division is the odd one out.
To divide by \(a\) is to multiply by its inverse: a number \(x\) with \(ax \equiv 1 \pmod m\). On the 7-hour clock \(3 \times 5 = 15 \equiv 1\), so 5 does the job of \(\tfrac13\). On the 6-hour clock \(2x\) only ever lands on 0, 2 or 4. It never reaches 1, so 2 has no inverse.
\(a\) has an inverse mod \(m\) exactly when \(a\) and \(m\) share no factor bigger than 1.
Why. If \(d > 1\) divides both \(a\) and \(m\), it divides \(ax - km\) for every \(x\) and \(k\), so that number is never 1. If they share no factor, Euclid's algorithm ends at 1, and running it backwards writes \(1 = ax + my\) for some whole numbers \(x, y\). Read that mod \(m\): \(ax \equiv 1\).
If \(m\) is a prime \(p\), none of \(1, 2, \dots, p - 1\) shares a factor with it. So everything except 0 has an inverse, and every division works.
Watch one: \(\tfrac17\) on a 40-hour clock
Run Euclid's algorithm on 40 and 7, keeping every line:
\[40 = 5 \times 7 + 5, \qquad 7 = 1 \times 5 + 2, \qquad 5 = 2 \times 2 + 1.\]
It ends at 1, so an inverse exists. Now climb back up, replacing each remainder by the line that made it:
\[1 = 5 - 2 \times 2 = 5 - 2(7 - 5) = 3 \times 5 - 2 \times 7 = 3(40 - 5 \times 7) - 2 \times 7 = 3 \times 40 - 17 \times 7.\]
So \(7 \times (-17) \equiv 1 \pmod{40}\), and \(-17 \equiv 23\). Check: \(7 \times 23 = 161 = 4 \times 40 + 1\). To solve \(7x \equiv 3\), multiply both sides by 23: \(x \equiv 69 \equiv 29\).
An RSA private key is found exactly this way: \(d\) is the inverse of \(e\). Pick two primes and watch Euclid find it at mathdetours.com/demos/rsa.html.
Your turn
- Find the inverse of each of 1, 2, 3, 4, 5, 6 on the 7-hour clock. Then work out \(4 \div 3 \pmod 7\).
- Which of \(1, 2, \dots, 11\) have an inverse mod 12? Find each inverse. What do you notice?
- Use Euclid's algorithm to find the inverse of 11 mod 26. Then solve \(11x \equiv 5 \pmod{26}\).
- Among \(0, 1, \dots, 5\), find every solution of \(2x \equiv 4 \pmod 6\), and of \(2x \equiv 3 \pmod 6\). "Divide both sides by 2" gives \(x \equiv 2 \pmod 6\) for the first. What did it miss, and what is the correct statement?
Stretch: Wilson's theorem
On the 11-hour clock, pair each of \(2, 3, \dots, 9\) with its inverse. Use the pairs to find the remainder of \(10! = 10 \times 9 \times \dots \times 1\) on division by 11 without multiplying it out. What should \((p - 1)!\) leave for any prime \(p\)?
Answers
- \(1 \to 1\), \(2 \to 4\), \(3 \to 5\), \(4 \to 2\), \(5 \to 3\), \(6 \to 6\). Then \(4 \div 3 \equiv 4 \times 5 = 20 \equiv 6\). Check: \(3 \times 6 = 18 \equiv 4\).
- Only 1, 5, 7 and 11, the numbers sharing no factor with 12. Each is its own inverse: \(5 \times 5 = 25\), \(7 \times 7 = 49\) and \(11 \times 11 = 121\) all leave remainder 1.
- \(26 = 2 \times 11 + 4\), \(11 = 2 \times 4 + 3\), \(4 = 1 \times 3 + 1\). Back up: \(1 = 4 - 3 = 4 - (11 - 2 \times 4) = 3 \times 4 - 11 = 3(26 - 2 \times 11) - 11 = 3 \times 26 - 7 \times 11\). So the inverse is \(-7 \equiv 19\); check \(11 \times 19 = 209 = 8 \times 26 + 1\). Then \(x \equiv 19 \times 5 = 95 \equiv 17\); check \(11 \times 17 = 187 = 7 \times 26 + 5\).
- \(2x \equiv 4\): \(x = 2\) and \(x = 5\). \(2x \equiv 3\): no solution, since \(2x\) is 0, 2 or 4. Dividing by 2 missed \(x = 5\). The 2 has no inverse mod 6, so it cannot be cancelled. Correctly: \(2x - 4 = 6k\) means \(x - 2 = 3k\), so \(x \equiv 2 \pmod 3\). The modulus must be divided too.
Stretch. The pairs are \((2, 6)\), \((3, 4)\), \((5, 9)\), \((7, 8)\): each product is \(\equiv 1\). That leaves 1 and 10, so \(10! \equiv 1 \times 10 \equiv 10 \equiv -1 \pmod{11}\). For any prime \(p\): a number is its own inverse when \(x^2 \equiv 1\), so \(p\) divides \((x - 1)(x + 1)\), so \(x \equiv 1\) or \(x \equiv p - 1\). Everything else pairs off, and \((p - 1)! \equiv p - 1 \equiv -1 \pmod p\). This is Wilson's theorem.