Divisibility by 6: Criterion and Consequence

Divisibility proofs are a cornerstone of the HSC Extension 2 Number and Proofs topic, challenging you to combine logical reasoning with algebraic manipulation. In this problem, we tackle the biconditional criterion for divisibility by 6—showing that a number is divisible by 6 exactly when it’s divisible by both 2 and 3—and then apply it to prove the classic result that $n^3-n$ is always a multiple of 6. By working through the solution, you’ll sharpen your ability to split a composite divisor into coprime factors and exploit the structure of consecutive integers.

Problem Statement

For $n \in \mathbb{Z}$, prove that:

• $n$ is divisible by 6 if and only if $n$ is divisible by 2 and 3.
• $n^3 - n$ is divisible by 6.

---

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

Part (a): Biconditional Proof

A biconditional statement requires proof in both directions. We first show that if 6 divides $n$, then $n$ must be divisible by 2 and 3; then we prove the converse, establishing the equivalence.

Forward ($\implies$): If $6 \mid n$, then $2 \mid n$ and $3 \mid n$.

Proof:

Assume $6 \mid n$. Then $n = 6k$ for some integer $k$.

We factor the expression to extract the required divisors: Write $n = 6k = 2(3k)$. Since $3k$ is an integer, $2 \mid n$.

Write $n = 6k = 3(2k)$. Since $2k$ is an integer, $3 \mid n$.

Reverse ($\impliedby$): If $2 \mid n$ and $3 \mid n$, then $6 \mid n$.

Now we assume $n$ is divisible by both 2 and 3, and we’ll show that 6 must divide $n$. Because 2 and 3 are coprime, this implication relies on showing that $n$ can be written as a multiple of 6.

Proof:

Assume $2 \mid n$ and $3 \mid n$.

Then $n = 2a$ and $n = 3b$ for some integers $a, b$.

From $n = 2a$, $n$ is even. From $n = 3b$, we have $2a = 3b$.

Since LHS is even, RHS $3b$ must be even. Since 3 is odd, $b$ must be even.

This parity argument is the key: because 3 is odd, the factor 2 must come from $b$. Write $b = 2c$ for some integer $c$.

Then:

$$n = 3b = 3(2c) = 6c$$

Since $c$ is an integer, $6 \mid n$.

Part (b): Using Part (a)

Goal: Prove $6 \mid (n^3 - n)$.

Rather than trying to divide $n^3-n$ by 6 directly, we’ll use the criterion from part (a): if we can show the expression is divisible by 2 and 3 (which are coprime), then 6 divides it automatically.

By part (a), sufficient to show $2 \mid (n^3 - n)$ and $3 \mid (n^3 - n)$.

Step 1: Factor

A clever factorisation unlocks the whole proof:

$$n^3 - n = n(n^2 - 1) = n(n-1)(n+1) = (n-1)n(n+1)$$

This is the product of three consecutive integers.

Step 2: Prove $2 \mid (n^3 - n)$

Because integers alternate between even and odd, any three consecutive numbers must contain at least one even number. Among any three consecutive integers, at least one is even.

Therefore, $(n-1)n(n+1)$ contains an even factor, so $2 \mid (n^3 - n)$.

Step 3: Prove $3 \mid (n^3 - n)$

Multiples of 3 appear every third integer, so exactly one in any block of three consecutive numbers is a multiple of 3. Among any three consecutive integers, exactly one is divisible by 3.

Therefore, $(n-1)n(n+1)$ contains a factor divisible by 3, so $3 \mid (n^3 - n)$.

Conclusion

Now we have both divisibility conditions satisfied, and since 2 and 3 are coprime, part (a) gives the final result:

Since $2 \mid (n^3 - n)$ and $3 \mid (n^3 - n)$, and $\gcd(2,3) = 1$, by part (a):

$$6 \mid (n^3 - n)$$

---

Takeaways

• Coprime Divisibility: If $\gcd(a,b) = 1$ and both $a \mid n$ and $b \mid n$, then $ab \mid n$
• Consecutive Integer Properties: Among $k$ consecutive integers, exactly one is divisible by $k$
• Multi-part Strategy: Part (b) leverages part (a) to simplify proof (check divisibility by 2 and 3 separately)
• Factorization: $n^3 - n = (n-1)n(n+1)$ reveals structure as consecutive integer product

---

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 Combinatorics, HSC Polynomials