Sophia,
a) Determine the remainder when 2^{2009} + 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^{99} + 61^{100} is divisible by 31;
Do this in much the same way. Remember that if 30^{99} has remainder A and 61^{100} has remainder B, then their sum has the same remainder as A+B does.
c) It is known that numbers p and 8p^{2}+1 are primes. Find p.
 Experiment. You will find one answer fairly quickly. But you're not done yet...in math we prove things
 What do you notice about all your other values of 8p^{2}+1? (If you are making sensible use of divisibility tests to see if the numbers you get are prime, you may notice something interesting.)
 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^{1}, 2^{9}, 2^{17},...,2^{2009} 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^{1}, 2^{9}, 2^{17},...,2^{2009} ?
Note that the remainder from A multiplied by the remainder from B is equal to the remainder from AB.
2^{8} gave a remainder of 1 when divided by 17, so 2^{9} has a remainder of 2, 2^{10} 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^{1} = 2 and 2^{2009} 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^{1}, 30^{2}, 30^{3}... 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^{99} 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^{2}? 8p^{2}? 8p^{2} + 1? And what else does this tell you about 8p^{2} + 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
 2, 2^{9}, 2^{17},...,2^{2009} all have remainders of 2 when divided by 17, so 2^{2009}+1 has a remainder of 2+1 = 3.
 30^{2} = 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^{99} + 61^{100} has the same remainder as 30+1, which is 0.
 "It is known that p and 8p^{2}+1 are primes. Find p."
Experiment shows that (3,73) works. More experiment shows that every other number of the form 8p^{2}+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^{2} has the same remainder (on dividing by 3) as 1^{2} = 1 or 2^{2} =4 : that is, 1 in each case. 8q^{2}+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
