Prove that for all odd integer $n, n^{4}=1\pmod {16}$ My answer: $n=2k+1$ 
$n^{4}=(2k+1)^{4}$=$16k^{4}+32k^{3}+8k^{2}+24k+1$.
I do not know how to conclude; really needed help here.
 A: Hint:
$$(2k+1)^4=16k^4+32k^3+24k^2+8k+1$$
$$=16(k^4+2k^3)+8k(1+3k)+1$$
It is now sufficient to prove that $k(1+3k)$ is always even.
A: If $k\in\mathbb Z$, then by Binomial theorem: $$(2k+1)^4=16k^4+32k^3+24k^2+8k+1$$
$$=16\left(k^4+2k^3+k^2+\frac{k(k+1)}{2}\right)+1$$
$\frac{k(k+1)}{2}$ is an integer, because $k,k+1$ are consecutive integers, so $k(k+1)$ is even.
A: For odd integers, $n$, there are these cases,
$$n\equiv 1, 3, 5, 7, 9, 11, 13, 15 \ (\rm mod 16)$$
Rewrite:
$$n\equiv \pm 1, \pm 3, \pm 5, \pm 7 \ (\rm mod 16)$$
This is since 9, 11, 13, 15 are congruent to -7, -5, -3, -1, respectively.
Now we square both sides,
$$n^2 \equiv 1, 9, 25, 49 \ (\rm mod 16)$$
Rewrite it again:
$$n^2 \equiv 1, -7 \ (\rm mod 16)$$
This is because 25 is congruent to 9 (which is congruent to -7) and 49 is congruent to 1.
Square both sides again;
$$n^4  \equiv  1, 49  \equiv 1\   (\rm mod 16)$$
Now we have the desired result.
A: $$n^4-1=(n^2+1)(n+1)(n-1)$$
If $n$ is odd, then all the factors are even, and one of the factors $(n+1)$ or $(n-1)$ is divisible by $4$. Hence $2^4|n^4-1$, or in other words $n^4\equiv1\pmod{16}$.
This can be generalized to see that $n^{2^k}\equiv1\pmod{2^{k+2}}$ for odd $n$:
$$n^{2^k}-1=\left(\left(n^{2^{k-1}}+1\right)\left(n^{2^{k-2}}+1\right)\cdots\left(n+1\right)\right)\left(n-1\right)$$
Since $x$ is odd, all the $k+1$ factors in the above are even, and either $(n+1)$ or $(n-1$) is divisible by $4$, so $2^{k+2}|n^{2^k}-1$. 
A: $$(2a+1)^2=8\cdot\dfrac{a(a+1)}2+1=8b+1\text{(say)}$$
$$(8b+1)^2=64b^2+16b+1=16(4b^2+b)+1$$
A: Well everyone has their own solution but here is mine
We are asked to prove 
$A =n^4 -1 = 0( mod 16)$
$A = (n+1)(n-1)(n^2 +1)$
Now n is given to be an odd number
So 
$n = 4k +1$ or $ 4k -1$
Lets take case (1)  $ n = 4k +1$
We get 
$A = (4k +2)(4k)(16k^2 +8k +2)$
Taking our the common factors
We get 
$A = 16m$
Likewise for case(2)
We get 
$A = 16 n$
So we get 
$A= 0(mod 16)$
Which I believe we wanted to prove
A: $$n^{4}=(2k+1)^{4}=16k^{4}+32k^{3}+8k^{2}+24k+1=\underbrace{16k^{4}+32k^{3}}_{16q_1}+8k(k+3)+1$$
Now if $k=2m$ we have $8k(k+3)=16q_2$ and $k=2m+1$ then $8k(k+3)=16q_2$, therefore 
$$n^{4}=(2k+1)^{4}=16k^{4}+32k^{3}+8k^{2}+24k+1=16q_1+16q_2+1=16q+1$$
A: let $ n = 2k + 1$, $n^4 \equiv 16(k^2+k)^2+8(k^2+k)+1 \equiv 8(k^2+k)+1 \pmod {16}$
case $1$: $k$ is an even(i.e. $k = 2m$), it suggests that  $8(k^2+k)+1 = 16(2m^2+m)+1$
case $2$: $k$ is an odd(i.e. $k = 2m+1$), it suggests that $8(k^2+k)+1 = 16(2m+1)(m+1)+1$
A: Alternatively, you can simply consider the following cases:


*

*$n\equiv 1\pmod{16} \implies n^4\equiv 1^4\equiv   1\equiv1\pmod{16}$

*$n\equiv 3\pmod{16} \implies n^4\equiv 3^4\equiv  81\equiv1\pmod{16}$

*$n\equiv 5\pmod{16} \implies n^4\equiv 5^4\equiv 625\equiv1\pmod{16}$

*$n\equiv 7\pmod{16} \implies n^4\equiv 7^4\equiv2401\equiv1\pmod{16}$

*$n\equiv 9\pmod{16} \implies n^4\equiv 9^4\equiv(16-7)^4\equiv(-7)^4\equiv7^4\equiv\ldots$

*$n\equiv11\pmod{16} \implies n^4\equiv11^4\equiv(16-5)^4\equiv(-5)^4\equiv5^4\equiv\ldots$

*$n\equiv13\pmod{16} \implies n^4\equiv13^4\equiv(16-3)^4\equiv(-3)^4\equiv3^4\equiv\ldots$

*$n\equiv15\pmod{16} \implies n^4\equiv15^4\equiv(16-1)^4\equiv(-1)^4\equiv1^4\equiv\ldots$

A: Let $m=n-1$
$n^4 = m^4+4m^3+6m^2+4m^1+1$
Since $m$ is even, $m=2x$ for some $x\in\mathbb{N}$
$\implies n^4=2^4x^4+4\times2^3x^3+6\times2^2x^2+4\times2x+1$
$16x^4, 32x^3$ are both $0($mod $16)$, leaving $6\times2^2x^2+4\times2x+1$.
If $x$ is odd, $3x+1$ must be even, therefore $8x(3x+1)$ is $0($ mod $16)$.
If $x$ is even, $8x$ must be $0($ mod $16)$.
$\implies n^4=0($ mod $16)$
A: $$n^4-1=(n^2-1)(n^2+1)=(n-1)(n+1)(n^2+1)$$
Now, $n-1,n+1$ are two consecutive even integers. Therefore, one is divisible by $4$ and the other is even. Also, $(n^2+1)$ is even. 
Therefore, the product is divisible by $4 \cdot 2 \cdot 2=16$. 
A: A slight variation...
For all odd $n$, $n^2 \equiv 1 \bmod 8 \implies n^2 \equiv \{1,9\} \bmod 16$ 
Since $9^2 \equiv 1 \bmod 16$, odd $n \implies n^4 \equiv 1 \bmod 16$.
A: Let $a_n = (2n+1)^4-1$. The repeated differences are
$$
\begin{array}{llllll}
0 & 80 & 624 & 2400 & 6560 & 14640 & \\
80 & 544 & 1776 & 4160 & 8080 & \\
464 & 1232 & 2384 & 3920 & \\
768 & 1152 & 1536 & \\
384 & 384 & \\
0 & \\
\end{array}
$$
and so Newton's interpolation formula gives
$$
(2n+1)^4-1 =
0 \binom{n}{0} + 80 \binom{n}{1} + 464 \binom{n}{2} + 768 \binom{n}{3} + 384 \binom{n}{4}
$$
Since $0, 80, 464, 768, 384$ are all multiples of $16$, we get the result.
This computation also shows that it is enough to verify that $16$ divides $a_n$ for $n=0,1,2,3,4$ because then $16$ divides all differences.
