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
_____________________________________________

Showing Divisibility


Date: 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/   
    
Associated Topics:
High School Discrete Mathematics
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/