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
Math Forum Home || Math Library || Quick Reference || Math Forum Search