Divisibility of n Squared Minus One by Three

Divisibility arguments are a staple of the HSC Extension 1 proofs topic, testing your ability to reason about integers and their remainders. In this problem we explore the property that $n^2-1$ is divisible by $3$ precisely when $n$ itself is not a multiple of $3$. Working through the proof will sharpen your skills with modular arithmetic and proof by cases, two fundamental tools for tackling number-theoretic statements.

Problem Statement

Prove that $n^2 - 1$ is divisible by 3 if $n$ is not a multiple of 3.

---

Hints

Attempt the proof independently first. Focus on the key theorem, algebraic transformation, or contradiction setup that links the hypothesis to the target conclusion.

---

Solutions

Proof by Cases (Modular Arithmetic)

Step 1: Set up the cases

If $n$ is not a multiple of 3, then $n \not\equiv 0 \pmod{3}$.

By the division algorithm, $n$ must satisfy one of:

• $n \equiv 1 \pmod{3}$, or
• $n \equiv 2 \pmod{3}$

We will prove $n^2 - 1 \equiv 0 \pmod{3}$ in both cases.

Step 2: Case 1 - $n \equiv 1 \pmod{3}$

For the first case, we substitute $n \equiv 1$ into $n^2-1$ and reduce modulo 3:

$$\begin{aligned} n^2 - 1 &\equiv (1)^2 - 1 \pmod{3} \\ &\equiv 1 - 1 \pmod{3} \\ &\equiv 0 \pmod{3} \end{aligned}$$

Therefore, $3 \mid (n^2 - 1)$ in this case.

Step 3: Case 2 - $n \equiv 2 \pmod{3}$

In this case, we substitute $n \equiv 2$ and simplify, remembering that $4 \equiv 1 \pmod{3}$:

$$\begin{aligned} n^2 - 1 &\equiv (2)^2 - 1 \pmod{3} \\ &\equiv 4 - 1 \pmod{3} \\ &\equiv 3 \pmod{3} \\ &\equiv 0 \pmod{3} \end{aligned}$$

Therefore, $3 \mid (n^2 - 1)$ in this case as well.

Conclusion

Since $n^2 - 1 \equiv 0 \pmod{3}$ in all possible cases where $3 \nmid n$, we conclude that $n^2 - 1$ is divisible by 3 whenever $n$ is not a multiple of 3.

---

Takeaways

• Proof by Cases Setup: If $n \not\equiv 0 \pmod{m}$, check all other residue classes modulo $m$
• Modular Arithmetic: Use $a \equiv b \pmod{m}$ to mean $m \mid (a-b)$, or equivalently, $a$ and $b$ have same remainder when divided by $m$
• Complete Case Coverage: For modulo 3, only residues are 0, 1, 2; excluding 0 leaves exactly 2 cases to check
• Calculation Technique: Substitute residue values directly: if $n \equiv 2 \pmod{3}$, then $n^2 \equiv 4 \equiv 1 \pmod{3}$

---

Further Readings

If you found this proof interesting, be sure to check out these relevant HSC booklets to sharpen your reasoning skills: HSC Proofs, HSC Mechanics, HSC Combinatorics