Showing DivisibilityDate: 07/12/98 at 20:42:44 From: Scott Mills Subject: Congruence Theory I am stumped. I must show that 7 divides 5^(2n) + 3(2^(2n+1)). How do I begin? Thanks! Scott Mills Date: 07/13/98 at 18:21:08 From: Doctor Pete Subject: Re: Congruence Theory Hi Scott, Since we want to show that this expression is divisible by 7, a good place to start is to write the expression in terms of multiples of 7. So we write: 5^(2n) + 3(2^(2n+1)) = 25^n + 6(4^n) = (3*7 + 4)^n + (7-1)(4^n) = (3*7 + 4)^n + 7(4^n) - 4^n Now, the Binomial Theorem applied to (3*7 + 4)^n shows that: (3*7 + 4)^n == 4^n (mod 7) Here, == is used to mean "is congruent to." To see why, note that in the binomial expansion of (x + y)^n, every term except y^n is divisible by x. Hence (x + y)^n == y^n (mod x). Now, since 7(4^n) == 0 (mod 7), we find that: (3*7 + 4)^n + 7(4^n) - 4^n == (4^n) + 0 - (4^n) (mod 7) == 0 (mod 7) This shows divisibility by 7. The idea of using the Binomial Theorem is a subtle one, but it is easily reasoned. There are other ways of solving the problem, I'm sure, but this was the first solution that came to mind. Best wishes, - Doctor Pete, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/