Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/