Divisibility of a number of the form $4^n-1$ with large $n$

Question

I came across a question which was $4^{1000} -1$ is divisible by ...".

I tried the dividing tricks, but I couldn't do it because the number was too large.

Answer 1

Hint

$$4^{1000}-1=2^{2000}-1=(2^{1000}-1)\cdot (2^{1000}+1).$$

Answer 2

Note: $\frac {x^k - 1}{x-1} = x^{k-1}+ .... + 1$ so $x-1|x^k - 1$ and so $2^k - 1|2^{km} - 1$.

So $4^{1000} - 1 = 2^{2000} -1$ .

So if $k | 2000=2^4*5^3$ then $2^k -1|2^{2000} -1$.

So $2^k - 1$ is divisor for $k = 1,2,4,8,16,5,10,20,40,80,25,50,100,200,400,125,250,500,1000,2000$

Note: $\frac {x^2n - 1}{x + 1} = x^{2n-1}-x^{2n-2}+...-x^2+x - 1$

So for $k|1000$ then $2^k + 1|2^{2000} - 1$ which holds for $1,2,4,8,5,10,20,40,25,50,100,200,125,250,500,1000$.

So those are a lot of factors!

But there are more.

For each $k|n$ and $n|2000$ then $1 + 2^k + 2^{2k} + ..... + 2^{n-k}$ is a factor.

As is $2^{n-k} - .... -2^{2k} + 2^k -1$ if $k|2n$ and $n|2000$.

So for example $31 = 2^5 -1$ and $33 = 2^5 + 1$ are both factors as are .... lots of things. Also $2^8 \pm 1 = 63,65$ etc. $13=1+4+8$. ($11$ seems to be a lucky accident as $2^5 + 1$ wasn't prime.) Way too many to list.