divisibility problem cant use module just inductionby Willy_Will Tags: divisibility, induction, module 

#1
Mar1807, 02:03 PM

P: 15

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 



#2
Mar1807, 02:05 PM

Sci Advisor
HW Helper
P: 9,398

If 5 divides X and you show that 5 divides YX, does 5 divide Y?




#3
Mar1807, 02:12 PM

P: 15

I think so, but how can I use that in my problem?




#4
Mar1807, 06:14 PM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,882

divisibility problem cant use module just induction
The fact that 8= 5+ 3 is very useful here!




#5
Mar1807, 09:04 PM

P: 15

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 



#6
Mar1807, 09:11 PM

P: 15

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 



#7
Mar1807, 09:13 PM

P: 15

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 



#8
Mar1907, 06:48 AM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,882

By George, I think he's got it!




#9
Mar1907, 07:24 AM

P: 15

Thanks guys, I really appreciate it!!



Register to reply 
Related Discussions  
divisibility problem  Linear & Abstract Algebra  1  
Proof by mathematical Induction: Divisibility  Math & Science Software  3  
Mathmatical Induction Problem (Divisibility)  Precalculus Mathematics Homework  2  
A module problem  Linear & Abstract Algebra  2  
space module problem  Introductory Physics Homework  2 