Prove that $n^4 \mod 8$ is identically equal to either 0 or 1, $\forall \ n\in \mathbb{N}$.

Question

I feel pretty confident about the first half of my solution for this, however I don't like how I used the induction hypothesis on the case for even integers, it feels like it isn't doing anything useful since it is really easy to show that $P(2x+2) \mod 8 \equiv 0$ without using the inductive hypothesis.

This is also the first semester I've been doing proofs, so am I going about this right?

Proof. Since $1^4 \mod 8 = 1$, $P(1)$ holds. Also, $2^4 \mod 8 = 16 \mod 8 = 0$ so, $P(2)$ holds.

We claim that $P(2x-1)$ holds, then $(2x-1)^4 \mod 8\equiv 1$ for any odd integer $n=2x-1$. So, $$(2x-1)^4 = 16x^4-32x^3+24x^2-8x+1 \mod 8\equiv 1,$$ now consider $$(2x+1)^4 = 16x^4+32x^3+24x^2+8x+1 = (16x^4-32x^3+24x^2-8x+1)+64x^3+16x,$$ then since $$64x^3+16x \mod 8 = 8(8x^3+2x) \mod 8 \equiv 0,$$ we conclude that $$(16x^4-32x^3+24x^2-8x+1)+64x^3+16x \mod 8 \equiv 1+0 = 1.$$ Thus, $P(2x+1)$ holds, and all odd integers $n$ hold.

Next, we claim that $P(2x)$ holds, then $(2x)^4 \mod 8\equiv 0$ for any even integer $n=2x$. So, $$(2x)^4 \mod 8 = 16x^4 \mod 8 \equiv 0,$$ now consider $$(2x+2)^4 = 16x^4+64x^3+96x^2+64x+16,$$ then $$64x^3+96x^2+64x+16 \mod 8 = 8(8x^3+12x^2+8x+2) \mod 8 \equiv 0,$$ we conclude that $$16x^4+64x^3+96x^2+64x+16 \mod 8 \equiv 0+0 = 0.$$ Thus, $P(2x)$ holds, and all even integers $n$ hold.

By mathematical induction, if $n=2x-1$ and $n=2x$ hold for the given statement, $n=2x+1$ and $n=2x+2$ also hold. Therefore, the statement holds for all $n \in \mathbb{N}$.

$\mathbb{QED}$

Answer 1

Your proof is unnecessarily complicated.

If $n$ is even, then we can say $n = 2k$

$(2k)^4 = 16k^4 = 8(2k^4)$ which is divisible by $8.$

$(2k)^4 \equiv 0 \pmod 8$

If $n$ is odd, then $n = 2k+1$

$(2k+1)^4 = 16k^4 + 4(2k)^3 + 6(2k)^2 + 4(2k)+ 1$

Each of the first $4$ terms is divisible by $8$

$(2k+1)^4 \equiv 1 \pmod 8$

Answer 2

The proof looks good, although as Doug M suggests, there are much easier ways to reach the same result. In particular, you're right to observe that you don't actually need the inductive hypothesis.

If you do want to apply induction, my advice is to start with a summary of your argument. Something like: "Let $P(n)$ be the claim. We will prove $P(1)$, $P(2)$, $P(2x-1)\implies P(2x+1)$, and $P(2x)\implies P(2x+2)$, completing a proof by induction."

Answer 3

Your idea is okay, but $(2x+2)^4=16 + 64 x + 96 x^2 + 64 x^3 + 16 x^4$,

unlike what you initially put in the question.

---

Alternatively, you could argue that if $2|n$ then $8|n^3|n^4$, so $n^4\equiv0\pmod8$,

and if $2\nmid n$ then $2|n-1, n+1, $ and $n^2+1$, so $8|n^4-1$; i.e., $n^4\equiv1\pmod8$.