Show there are infinitely many natural numbers $n$ such that $n$ divides $16^n-1$

Question

Show there exist infinitely many natural numbers $n$ such that $n\mid 16^n-1$.

Answer 1

I was exploring the idea of a modulus divisible by $5$ (because $\phi(5)=4$ which is the power of $2$ in the problem) when Peter commented with the right idea. So the credit belongs to that user. Indeed, since $$\phi(5^k)=5^k-5^{k-1}=4\cdot 5^{k-1},$$ Euler's congruence gives $$2^{4\cdot 5^{k-1}}\equiv 1\pmod{5^k}.$$ Then $$16^{5^{k-1}}\equiv 1\pmod{5^k}$$ and then you can just take the congruence to the power of $5.$

Answer 2

Here is a proof by induction that $3^k|16^{3^k}-1$.

Base case: $k=1: 3|16^3-1$.

Now assume $3^k|16^{3^k}-1$.

Note that $16^{3^{k+1}}-1=(16^{3^k}-1)(16^{2\cdot3^k}+16^{3^k}+1)$,

where the first factor is divisible by $3^k$ and the second factor is divisible by $3$,

so the product is divisible by $3^{k+1}$.