Bolaji Atanda won the prize.

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.

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 ▇

Alternative proof by induction (with Step 1 being the case n=0)

Step 1: prove true for n=0

0^{p}=0 for all p ▇

Step 2: prove true for n=k ⇒ true for n=k+1

From Pascal’s triangle:

(k+1)^{p} = k^{p} + 1^{p} + terms divisible by p

(Look at the 2nd, 3rd, 5th, 7th rows. All the numbers in them except the 1’s at the ends are divisible by 2, 3, 5, 7 or whatever. It’s not hard to prove this if you know a little of the maths of Pascal’s triangle, but just take it as a fact for now).

So (k+1)^{p} = k^{p} + 1 + terms divisible by p

But *if* the claim is true for n=k, then k^{p} = k + terms divisible by p

Therefore (k+1)^{p} = k + 1 + terms divisible by p ▇

Step 1 + Step 2 ⇒ true for all by induction.