Polynomial Divisible by 7Date: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/