Welcome to NRICH.

 
21000/3
By Marta Aguiar on Monday, February 15, 1999 - 08:51 pm:

From: Marta Aguiar, age 14, St Julian's School,
Carcavelos, Portugal

Can you solve this problem for me?

2 to the power of 1000 divided by 3 gives an answer
with what remainder?

Example: 7/4 has a remainder of 3

By Admin (Admin) on Monday, February 15, 1999 - 08:54 pm:


Dear Marta,

The way I solved this question was to start with small powers of 2, and build upwards, to see if I could see a pattern. You should realise that the answer certainly can't be 0 because 21000 has already been factorised into primes, and the prime 3 isn't present (which is both a necessary and sufficient condition for 3 to divide a number). If you try this method, you should quickly spot a pattern, and hence make a conjecture on what the answer should be.

To prove this, we need to use a little modular arithmetic:
We say that a number x is congruent to 1 modulo 3 (written x = 1 mod 3 except that the equals sign should have three lines) if x leaves a remainder 1 when divided by 3. This is equivalent to saying x = 3p + 1 for some whole number p.

Then 2x = 2p × 3 + 2 = 2 mod 3. In other words if 2x is congruent to 1 mod 3, then 2x+1 is congruent to 2 mod 3. You should be able to deal similarly with the case where 2x is congruent to 2 mod 3 (i.e. work out what 2x+1 is congruent to).

Now you can know three things:

  1. 2 = 2 mod 3
  2. If 2x = 1 mod 3 then 2x+1 = 2 mod 3
  3. If 2x = 2 mod 3 then 2x+1 = 1 mod 3 You have now proved your conjecture by what we call induction, since you know the result for x = 1 and whenever you know the result for x, you know it for x + 1. Thus you know it for x = 2, 3, ... and in your case, 1000.

    Please write back if you would like more explanation of factorising numbers into primes, modular arithmetic or proof by induction.

    Best wishes,

    Richard