Polynomial Divisible by 7

Date: 11/14/2001 at 06:48:14
From: Lindsay Cox
Subject: Number theory

I am completeing an assignment based on number theory.  I am stuck 
on the final question. I have to prove that

7 divides into 2^(3n+1) + 4^(3n+1) + 1

(where ^ means to the power of).

I am not sure where to start or how to complete this question.

Thank you,
Lindsay

Date: 11/14/2001 at 08:54:50
From: Doctor Jubal
Subject: Re: Number theory

Hi Lindsay,

Thanks for writing Dr. Math.

From the type of question you're asking, I'm going to assume that you 
have seen proofs by induction and modular modular arithmetic before.  
If I'm wrong about either of these, write back and I'll try to explain 
the proof in different terms.

The first thing we can prove here is that 2^(3n+1) is congruent to 2, 
modulo 7. We can do this by induction. First, let's use n = 0 as the 
basis for the induction proof (that means we just need to demonstrate 
that what we want to prove is true for n = 0). 

Well, 2^(3(0)+1) = 2^1 = 2.

Now we want to show that if 2^(3n+1) = 2 (mod 7) is true for n = k, 
then it also must be true for n = k+1.  First, let's observe that

  2^(3(k+1)+1) = 2^(3k+4) = 2^3 * 2^(3k+1) = 8 * 2^(3k+1)

But 8 is congruent to 1, modulo 7, so we can replace 8 with 1 (I'll 
use == for the congruency symbol).

  2^(3(k+1)+1) == 1 * 2^(3k+1) == 2^(3k+1)    (mod 7)

So 2^(3n+1) has the same congruency modulo 7 for any whole number.  
And we've already seen that it is congruent to 2 modulo 7 for n = 0, 
so it must be congruent to 2 modulo 7 for all n.

You can prove that 4^(3n+1) == 4 (mod 7) by a very similar process, 
but I'll leave it to you to fill in those details.

Then finally, we can use these two congruencies to write

  2^(3n+1) + 4^(3n+1) + 1 == 2 + 4 + 1 == 0    (mod 7)

Since the sum is congruent to 0 modulo 7 for all n, it must be 
divisible by 7 for all n.

Does this help?  Write back if you'd like to talk about this some
more, or if you have any other questions.

- Doctor Jubal, The Math Forum
  http://mathforum.org/dr.math/