How to prove why $(2n + 1)^{16} \bmod 64 = 1$?

Question

The title says it all :-)

I verified experimentally this and I'm stuck with the 16th power of $(2n + 1)$:

$$ 65536n^{16} + 524288n^{15} + 1966080n^{14} + 4587520n^{13} + 7454720n^{12} + 8945664n^{11} + 8200192n^{10} + 5857280n^{9} + 3294720n^{8} + 1464320n^{7} + 512512n^{6} + 139776n^{5} + 29120n^{4} + 4480n^{3} + 480n^{2} + 32n + 1 $$

Thanks!

Answer 1

$64$ divides $m^{16}-1=(m^8+1)(m^4+1)(m^2+1)(m+1)(m-1)$ if $m$ is odd,

because each term in that product is even, and $(m+1)$ or $(m-1)$ is divisible by $4$.

Answer 2

All the coefficients of your expression for $(2n+1)^{16}$ can be written as $64k_i$ where $k_i$ is an integer, for $1<i \leq 16$, except the following,

$$480 n^2 +32 n+1=32(15 n^2 +n) +1$$

Therefore, the resulting number is a multiple of 64, except for the single term equal 1.

Answer 3

Hint:

$$(2n+1)^2=8\cdot\dfrac{n(n+1)}2+1=8m+1$$

$$(2n+1)^4=(1+8m)^2=1+16m(1+4m)=1+16r$$

Can you take it from here?