Fortnightly maths prize for 24 March

Sharif Quansah and Hayden Leroux won prizes for partial answers.

The problem: Calculate the remainder when 23 is divided by 3
when 25 is divided by 5
when 27 is divided by 7
when 35 is divided by 5
when 37 is divided by 7
when 45 is divided by 5

Name the pattern you see. (And, for extra credit, prove that pattern continues to hold for bigger numbers).

Deduce what the remainders are when 211 and 311 are divided by 11

Deduce what the remainders are when 210 and 310 are divided by 11

Calculate the remainder when 2987654321×3876543210 is divided by 11.

The arithmetic of remainders, called clock arithmetic or modular arithmetic, is centuries old, but has found wide practical use just recently in security systems for ATMs.

clocklogo261497520_atm_275330c


Solution

If p is prime and a<p, then the remainder when ap is divided by p is a.

This is written apa mod p

Therefore ap−1≡1 mod p.

So the remainders=1 when 210 and 310 are divided by 11.

2987654321×3876543210≡2 mod 11

Proof that apa mod p for all p prime and all a<p

For every a<p, there are ap lists of length p of the numbers 1, 2,… a.

Of those lists, a consist of the same number repeated p times, 1111…1, or 2222…2, etc.

166px-proofs-of-fermats-little-theorem-bracelet2-svg

Classify the other lists into “necklaces” by joining the ends. Since each list has length p, and p is prime, i.e. has no divisors other than 1 and p, the list can’t be made up of repeated copies of the same sublist. Therefore two lists make the same “necklace” only if one is the same as the other, only shifted round by r positions with r<p, as e.g. 1 2 3 4 5 6 7 makes the same "necklace" as 3 4 5 6 7 1 2.

166px-proofs-of-fermats-little-theorem-bracelet1-svg

Therefore p different lists are classified into each "necklace".

Therefore total number of lists = a + a multiple of p

apa mod p ▇