# Prove this is divisible by 15

1. Jan 11, 2013

### cragar

1. The problem statement, all variables and given/known data
Prove $4^{2n}-1$ is divisible by 15 for all positive integers
3. 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 im 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.

2. Jan 11, 2013

### 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.

3. Jan 11, 2013

### 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$.

4. Jan 11, 2013

### jfgobin

You may also use the factorisation of:

$\left ( x^n - 1 \right ) = \left ( x - 1 \right ) \left ( x^{n-1} + \ldots + 1 \right )$

5. Jan 11, 2013

### Mentallic

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.

6. Jan 11, 2013

### physics kiddy

Well, I have found a solution :

Let us assume that 42n-1 is divisible by 15.
So, we have

16n-1 is divisible by 16-1 ....

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

7. Jan 11, 2013

### Mentallic

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

8. Jan 11, 2013

### 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.