Proving that 3^(6n)-2^(6n) is divisible by 8 using induction

  • Thread starter rg2004
  • Start date
  • #1
22
0

Homework Statement



I am to prove that [tex]3^{6n}-2^{6n}[/tex] is divisible by 35 for all n[tex]n\in\aleph[/tex] using induction.

Homework Equations



[tex]3^{6n}-2^{6n}=35x[/tex] where [tex]x\in\aleph[/tex] for all [tex]n\in\aleph[/tex] and


The Attempt at a Solution


Base:
[tex]3^{6(1)}-2^{6(1)}=35*x[/tex]
[tex]665=35x[/tex]
x=19
thus since 19 is an element of natural numbers the base case is true

Then I make this assumption
Assume:
[tex]3^{6k}-2^{6k}=35x[/tex]

Inductive step:
[tex]3^{6(k+1)}-2^{6(k+1)}=35x[/tex]
[tex]3^{6}3^{6k}-2^{6}2^{6k}=35x[/tex]

and i don't know where to go from here, i've tried lots of things, but i cant reduce it down to the assumption
 

Answers and Replies

  • #2
737
0
Do you know this fact: a (mod n) × b (mod n) = ab (mod n)?
 
  • #3
22
0
No i didn't know about that, and we haven't looked at modulus yet, so i'm not sure how to use it in this proof
 
  • #4
737
0
Ok. Then, suppose 36k = 35a+y. Then, 26k = 35b+y. (Why?) Substitute.
 
  • #5
22
0
im assuming it looks like this:

[tex]3^{6}3^{6k}-2^{6}2^{6k}=35x[/tex]

[tex](3^{6} mod 35) (3^{6k} mod 35) - (2^{6} mod 35) (2^{6k} mod 35)=0[/tex]

[tex]((29\cdot3^{6k}) mod 35) - ((29\cdot2^{6k}) mod 35)=0[/tex]

[tex]29(3^{6k} mod 35 - 2^{6k} mod 35)=0[/tex]

[tex](3^{6k} mod 35 - 2^{6k} mod 35)=0[/tex]
 
  • #6
737
0
That's right. You have to be careful when dividing both sides by the same thing in modular arithmetic, but it works out correctly this time. If you want to pursue this problem without explicitly using modular arithmetic, see my second post.
 
  • #7
22
0
Regarding post #4:

i see that
36k = 35a+y
26k = 35b+y
since any number can be expressed as a linear combination like you showed, but what allows us to assume that the remainder , y, are equivalent? Is it because we assume
36k - 26k =35x that we must conclude from this that the remainders are the same in order for them to subtract to zero?
 
  • #8
737
0
Exactly so. Otherwise, there would be a contradiction.
 
  • #9
22
0
Thank you!
 

Related Threads on Proving that 3^(6n)-2^(6n) is divisible by 8 using induction

Replies
18
Views
1K
Replies
3
Views
17K
Replies
7
Views
3K
Replies
2
Views
1K
Replies
3
Views
1K
Replies
17
Views
15K
Replies
4
Views
897
Replies
1
Views
782
  • Last Post
Replies
19
Views
13K
Top