Is 4^(2n)-1 Divisible by 15? Proving with Induction

[cragar]

Homework Statement

Prove 4^{2n}-1 is divisible by 15 for all positive integers

The Attempt at a Solution

Ok so I factor it into this
(2^n+1)(2^n-1)(4^n+1)
I know how to get the factor of 3 because we know
2^n is even so either 2^n+1 or 2^n-1 is divisible by 3 because we have 3 consecutive integers so at least one of them needs to be divisible by 3.
But I am not sure how to get the factor of 5.
I thought about squaring some of their components and looking how close they
are to 4^n+1.

 

[Fightfish]

Consider the cases when n is odd and n is even. You should be able to obtain a factor of 5 from different terms in each case.

 

[pasmith]

Did you not notice that 4^2 = 16 = 15 + 1?

That suggests a proof, by induction on n, that 4^{2n} = 15k_n + 1 for some integers k_1 = 1, k_2, k_3, \dots.

 

[jfgobin]

You may also use the factorisation of:

<br /> \left ( x^n - 1 \right ) = \left ( x - 1 \right ) \left ( x^{n-1} + \ldots + 1 \right )<br />
​

 

[Mentallic]

I don't think that thinking would get you to the solution.

Of course it would. Induction is a perfectly reasonable method of proof here.

Assume 4^{2k}-1=15N for some integer N, and now prove that 4^{2(k+1)}-1 is a multiple of 15.

 

[physics kiddy]

Well, I have found a solution :

Let us assume that 4²ⁿ-1 is divisible by 15.
So, we have

16ⁿ-1 is divisible by 16-1 ...

Since 16ⁿ-1 = 16ⁿ - 1ⁿ ... it takes the form of aⁿ-bⁿ is divisible by a-b. Just prove that it is possible and you have it ...

 

[Mentallic]

That's not exactly induction, but rather the method that jfgobin detailed, except that assuming 4²ⁿ-1 is divisible by 15 does absolutely nothing for your proof.

 

[halo31]

Yeah it requires proof by induction. Its pretty straight foward. You have a base case. Let n=1 and show it works. Then for the inductive case basically what you assume that
15|4^(2k)-1 where k ε Z. Moreover we want to show that 15|4^(2k+2)-1. Then rewrite the notation as such were 15r=4^(2k)-1 where rεZ and 15n=4^(2k+2)-1 where nεZ. Also notice that 15n=4^(2k+2)-1 is just 15n=4^(2k)*16. From there its pretty much easy.