divisibility problem cant use module just induction


by Willy_Will
Tags: divisibility, induction, module
Willy_Will
Willy_Will is offline
#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
Going nuts? Turkey looks to pistachios to heat new eco-city
Space-tested fluid flow concept advances infectious disease diagnoses
SpaceX launches supplies to space station (Update)
matt grime
matt grime is offline
#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
Willy_Will is offline
#3
Mar18-07, 02:12 PM
P: 15
I think so, but how can I use that in my problem?

HallsofIvy
HallsofIvy is online now
#4
Mar18-07, 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!
Willy_Will
Willy_Will is offline
#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
Willy_Will is offline
#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
Willy_Will is offline
#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
HallsofIvy is online now
#8
Mar19-07, 06:48 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,882
By George, I think he's got it!
Willy_Will
Willy_Will is offline
#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