Divisibility by 8

Date: 04/14/97 at 10:41:29
From: Marianne Unruh
Subject: Number theory

Show that, if n is a positive integer, then 5^n+2*3^(n-1) + 1 is 
divisible by 8.

Date: 04/14/97 at 22:47:53
From: Doctor Steven
Subject: Re: Number theory

Say we pick an even number for n.  Then we have 

  5^(2k) + 2*3^(2k-1) + 1 =
    25^k + 6*3^(2k-2) + 1 = 
    25^k + 6*9^(k-1) + 1.  

Note that 25 leaves a remainder of 1 when divided by 8, so 25^k leaves 
a remainder of one when divided by 8. 

Nine also leaves a remainder of one when divided by 8, so 9^(k-1) 
leaves a remainder of one when divided by 8 (since k >= to 1). 
And 1 of course leaves a remainder of 1 when divided by 8.  

So we have 1 + 6*1 + 1. When we look at the remainder of this number 
when divided by 8, 1 + 6*1 + 1 = 8  says the remainder of this number 
when divided by 8 is 8, so really it has no remainder. 

Therefore if n is even, it's divisible by 8.

Say we pick an odd number for n. Then n = 2k + 1, with k >= 0.
So we have 
  5^(2k + 1) + 2*3^(2k) + 1 = 
    5*5^(2k) + 2*9^(k) + 1 = 
     5*25^k  + 2*9^k + 1.  

25 leaves a remainder of 1 when divided by 8, and so does 9, so 
when we look at the remainder of this equation when divided by 8 we 
get:
         5*1 + 2*1 + 1 = 8

This says the number is divisible by 8 for n odd, so the number is 
divisible by eight in any case.

Hope this helps.

-Doctor Steven,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/