Sophia,

a) Determine the remainder when 2²⁰⁰⁹ + 1 is divided by 17;

Look at the remainder when the first 20 or so powers of 2 are divided by 17. You don't need to actually find all the powers:

2,4,8,16,15 [from 16*2=32],13[from 15*2 = 30],9,...
In a while you will see a pattern.

Now use this to answer the question.

b) Prove that 30⁹⁹ + 61¹⁰⁰ is divisible by 31;

Do this in much the same way. Remember that if 30⁹⁹ has remainder A and 61¹⁰⁰ has remainder B, then their sum has the same remainder as A+B does.

c) It is known that numbers p and 8p²+1 are primes. Find p.

1. Experiment. You will find one answer fairly quickly. But you're not done yet...in math we prove things
   
   
2. What do you notice about all your other values of 8p²+1? (If you are making sensible use of divisibility tests to see if the numbers you get are prime, you may notice something interesting.)
   
   
3. Now prove that this will always happen whenever p is prime. (Hint: this part is why this problem belongs with the other two.)

Good Hunting!
RD

Sophia wrote back

Hello,

Thank you for your suggestions. My son and I have spent time reading through your suggestions and have found that the sequence to the fist part is:, 4, 16, 15, 13, 9, 1. Now we are stuck at this level. What's next?

"the sequence to the fist part is:, 4, 16, 15, 13, 9, 1" ... and this repeats forever with a period of 8.
Thus 2¹, 2⁹, 2¹⁷,...,2²⁰⁰⁹ all have the same remainder upon dividing by 17.

The same principle lets you answer the second part easily, and will help with the third part.

-Good Hunting!
RD

How did you come up with the 2¹, 2⁹, 2¹⁷,...,2²⁰⁰⁹ ?

Note that the remainder from A multiplied by the remainder from B is equal to the remainder from AB.

2⁸ gave a remainder of 1 when divided by 17, so 2⁹ has a remainder of 2, 2¹⁰ has a remainder of 4, and so on - the pattern repeats every 8 steps forever.

So if P and Q have the same remainder when divided by 8, 2^P and 2^Q have the same remainder when divided by 17.

How do we calculate the answer from this?

1 and 2009 have the same remainder when divided by 8, so 2¹ = 2 and 2²⁰⁰⁹ have the same remainder (=2) when divided by 17.

How will this part of the question assist with the following two parts?

The second problem can be solved using exactly the same ideas (and the obvious fact that "divisible by 31" means "remainder = 0 when divided by 31". The sequence of remainders from 30¹, 30², 30³... divided by 31 is at least eventually periodic [in fact it has period 2 - can you think of an easy way to see this? It may help to think of 30 as "-1" in this context?] So what is the remainder when you divide 30⁹⁹ by 31? (And so on...)

The third problems needs a couple more ideas. If a _prime_ number is not 3, what can you say about its remainder when divided by 3? [Experiment!] So what can you say about the remainder (upon dividing by
3) from p²? 8p²? 8p² + 1? And what else does this tell you about 8p² + 1?

Good Hunting!
RD

However in part A there is a +1 in the equation, what happens to this?

The basic idea here is that remainders can be added, subtracted, or multiplied (and divided when the divisor is prime.) Thus the remainder from dividing 2^2009+1 by 17 is 1 greater than the remainder from dividing 2^2009 by 17 - unless that gives 17, in which case the remainder is 0.

-RD

Hello,

I and my son have exhausted ourselves in attempting to answer the Divisibility questions, even after your guidens.=0A=0ACan you please provide the answers in order for us to work backwards? My son has guessed part A's answer to be 2, Is this correct?

Your assistance to supply the answers is greatly appreciated.

Kind Regards,
Sophia

1. 2, 2⁹, 2¹⁷,...,2²⁰⁰⁹ all have remainders of 2 when divided by 17, so 2²⁰⁰⁹+1 has a remainder of 2+1 = 3.
   
   
2. 30² = 900 which has a remainder of 1 when divided by 31. So every odd power of 30 has a remainder of 30 when divided by 31, every even power has a remainder of 1.
   
   Powers of 60 (= 1x31+30) have the same pattern of remainders
   
   So 30⁹⁹ + 61¹⁰⁰ has the same remainder as 30+1, which is 0.
   
   
3. "It is known that p and 8p²+1 are primes. Find p."
   
   Experiment shows that (3,73) works. More experiment shows that every other number of the form 8p²+1 is divisible by 3. We try to prove this:
   
   Every prime number q except 3 has a remainder of 1 or 2 when divided by 3. q² has the same remainder (on dividing by 3) as 1² = 1 or 2² =4 : that is, 1 in each case. 8q²+1 thus has the same remainder as 1x8+1, which is 9. But this is divisible by 3 and cannot be prime. So p=3 is the unique solution.
   

-RD