Fortnightly maths prize for 23 September 2016

clocklogo2

Bolaji Atanda won the prize.

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.


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 ▇

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

Step 1: prove true for n=0

0p=0 for all p ▇

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

From Pascal’s triangle:

(k+1)p = kp + 1p + terms divisible by p

pascal

(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 = kp + 1 + terms divisible by p

But if the claim is true for n=k, then kp = k + terms divisible by p

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

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