Sharif Quansah and Hayden Leroux won prizes for partial answers.

The problem: Calculate the remainder when 2^{3} is divided by 3

when 2^{5} is divided by 5

when 2^{7} is divided by 7

when 3^{5} is divided by 5

when 3^{7} is divided by 7

when 4^{5} 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 2^{11} and 3^{11} are divided by 11

Deduce what the remainders are when 2^{10} and 3^{10} are divided by 11

Calculate the remainder when 2^{987654321}×3^{876543210} 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.

Solution

If p is prime and *a*<p, then the remainder when *a*^{p} is divided by p is *a*.

This is written *a*^{p}≡*a* mod p

Therefore *a*^{p−1}≡1 mod p.

So the remainders=1 when 2^{10} and 3^{10} are divided by 11.

2^{987654321}×3^{876543210}≡2 mod 11

*Proof that a^{p}≡a mod p for all p prime and all a<p*

For every *a*<p, there are *a*^{p} 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.

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.

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

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

*a*^{p}≡*a* mod p ▇