Register to reply

Divisibility problem cant use module just induction

by Willy_Will
Tags: divisibility, induction, module
Share this thread:
Willy_Will
#1
Mar18-07, 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
Phys.Org News Partner Science news on Phys.org
NASA team lays plans to observe new worlds
IHEP in China has ambitions for Higgs factory
Spinach could lead to alternative energy more powerful than Popeye
matt grime
#2
Mar18-07, 02:05 PM
Sci Advisor
HW Helper
P: 9,398
If 5 divides X and you show that 5 divides Y-X, does 5 divide Y?
Willy_Will
#3
Mar18-07, 02:12 PM
P: 15
I think so, but how can I use that in my problem?

HallsofIvy
#4
Mar18-07, 06:14 PM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,310
Divisibility problem cant use module just induction

The fact that 8= 5+ 3 is very useful here!
Willy_Will
#5
Mar18-07, 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
Willy_Will
#6
Mar18-07, 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
Willy_Will
#7
Mar18-07, 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
HallsofIvy
#8
Mar19-07, 06:48 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,310
By George, I think he's got it!
Willy_Will
#9
Mar19-07, 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