## divisibility problem cant use module just induction

Hi all,

Great forum, I have been reading some cool stuff here for about a month.

Heres my question:
Using induction prove that 5 divides 8^n - 3^n, n Natural Number.

I know its true for n = 1, but I get stuck on the n = k+1. I dont know how to proceed from here: 8(8^k) - 3(3^k)

Also, I KNOW this is very easy using mod 5 but I can't do it here, I HAVE to prove it using only induction.

Any hints?

Thanks,

-William
 Recognitions: Homework Help Science Advisor If 5 divides X and you show that 5 divides Y-X, does 5 divide Y?
 I think so, but how can I use that in my problem?

Recognitions:
Gold Member
Staff Emeritus

## divisibility problem cant use module just induction

The fact that 8= 5+ 3 is very useful here!
 I think I've got it. Suppose that 5 divides 8^k - 3^k ---> 8^k - 3^k = 5x, for some integer x. case n = k +1 = 8^k+1 - 3^k+1 = 8(8^k) - 3(3^k) = 8(8^k) - (3^k)(8) + (3^k)(8) - (3)(3^k) = 8(8^k - 3^k) + 3^k(8 - 3) (1) (2) (1) by hypotesis 5 divides the expresion. (2) 5 = 8 - 3, 5 divides 5. = 8(5x) + 3^k(5) = 5(8x + 3^k) 5 divides the expresion Please tell me its that way, if not, point the errors and some hints. Thanks, really. -William
 I think I've got it. Suppose that 5 divides 8^k - 3^k ---> 8^k - 3^k = 5x, for some integer x. case n = k +1 = 8^k+1 - 3^k+1 = 8(8^k) - 3(3^k) = 8(8^k) - (3^k)(8) + (3^k)(8) - (3)(3^k) = 8(8^k - 3^k) + 3^k(8 - 3) (1) (2) (1) by hypotesis 5 divides the expresion. (2) 5 = 8 - 3, 5 divides 5. = 8(5x) + 3^k(5) = 5(8x + 3^k) 5 divides the expresion Please tell me its that way, if not, point the errors and some hints. Thanks, really. -William
 sorry for the double post. (1) = (8^k - 3^k) (2) = (8 - 3) (1) by hypotesis 5 divides the expresion. (2) 5 = 8 - 3, 5 divides 5. = 8(5x) + 3^k(5) = 5(8x + 3^k) 5 divides the expresion
 Recognitions: Gold Member Science Advisor Staff Emeritus By George, I think he's got it!
 Thanks guys, I really appreciate it!!