Logo
Published on

Divisibility of n Squared Minus One by Three

Authors
  • avatar
    Name
    Vu Hung
    Twitter

Problem Statement

Prove that n2−1n^2 - 1 is divisible by 3 if nn 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 nn is not a multiple of 3, then n≢0(mod3)n \not\equiv 0 \pmod{3}.

By the division algorithm, nn must satisfy one of:

  • n≡1(mod3)n \equiv 1 \pmod{3}, or
  • n≡2(mod3)n \equiv 2 \pmod{3}

We will prove n2−1≡0(mod3)n^2 - 1 \equiv 0 \pmod{3} in both cases.

Step 2: Case 1 - n≡1(mod3)n \equiv 1 \pmod{3}

n2−1≡(1)2−1(mod3)≡1−1(mod3)≡0(mod3)\begin{aligned} n^2 - 1 &\equiv (1)^2 - 1 \pmod{3} \\ &\equiv 1 - 1 \pmod{3} \\ &\equiv 0 \pmod{3} \end{aligned}

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

Step 3: Case 2 - n≡2(mod3)n \equiv 2 \pmod{3}

n2−1≡(2)2−1(mod3)≡4−1(mod3)≡3(mod3)≡0(mod3)\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∣(n2−1)3 \mid (n^2 - 1) in this case as well.

Conclusion

Since n2−1≡0(mod3)n^2 - 1 \equiv 0 \pmod{3} in all possible cases where 3∤n3 \nmid n, we conclude that n2−1n^2 - 1 is divisible by 3 whenever nn is not a multiple of 3.

\hfill □\square

Takeaways

  • Proof by Cases Setup: If n≢0(modm)n \not\equiv 0 \pmod{m}, check all other residue classes modulo mm
  • Modular Arithmetic: Use a≡b(modm)a \equiv b \pmod{m} to mean m∣(a−b)m \mid (a-b), or equivalently, aa and bb have same remainder when divided by mm
  • 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≡2(mod3)n \equiv 2 \pmod{3}, then n2≡4≡1(mod3)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:

Connect with me

If you're eager for more HSC Maths insights, be sure to check out my GitHub. For deeper dives and regular tips, join my Instagram. Let's tackle these challenging math problems together! You can also catch my daily math content on LinkedIn.