   SEARCH HOME Math Central Quandaries & Queries  Question from Sophia, a parent: Hello Please help my son with the solutions to the following: a) Determine the remainder when 2^2009 + 1 is divided by 17; b) Prove that 30^99 + 61^100 is divisible by 31; c) It is known that numbers p and 8p^2+1 are primes. Find p. Again, your assistance is greatly appreciated. Thanks Sophia Sophia,

a) Determine the remainder when 22009 + 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 3099 + 61100 is divisible by 31;

Do this in much the same way. Remember that if 3099 has remainder A and 61100 has remainder B, then their sum has the same remainder as A+B does.

c) It is known that numbers p and 8p2+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 8p2+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 21, 29, 217,...,22009 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 21, 29, 217,...,22009 ?

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

28 gave a remainder of 1 when divided by 17, so 29 has a remainder of 2, 210 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, 2P and 2Q 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 21 = 2 and 22009 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 301, 302, 303... 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 3099 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 p2? 8p2? 8p2 + 1? And what else does this tell you about 8p2 + 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?

Kind Regards,
Sophia

1. 2, 29, 217,...,22009 all have remainders of 2 when divided by 17, so 22009+1 has a remainder of 2+1 = 3.

2. 302 = 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 3099 + 61100 has the same remainder as 30+1, which is 0.

3. "It is known that p and 8p2+1 are primes. Find p."

Experiment shows that (3,73) works. More experiment shows that every other number of the form 8p2+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. q2 has the same remainder (on dividing by 3) as 12 = 1 or 22 =4 : that is, 1 in each case. 8q2+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     Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.