Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/