Divisibility of a Product

Today we examine a classic divisibility trap that often appears in HSC Extension 1 proofs. The statement looks plausible at first glance—if a divides a product, surely it must divide one of the factors? By working through this problem, you'll sharpen your ability to test claims with counterexamples and deepen your understanding of prime factorisation, a skill that directly supports the Proofs topic.

Problem Statement

Prove that for all positive integers $a, b,$ and $c$, if $a$ divides the product $bc$, then $a$ divides $b$ or $a$ divides $c$.

---

Hints

Attempt to set up a direct proof using the definition of divisibility: $bc = ak$ for some integer $k$. Can you algebraically force $a$ to divide $b$ or $c$?

Wait—is this statement actually true? Try testing it with some small integer values. What happens if $a$ is a composite number (like $4$ or $6$) rather than a prime number?

Exam Strategy: If you ever encounter an exam question that seems fundamentally incorrect or impossible, do not leave the page blank! A blank page guarantees 0 marks. Instead, prove that the statement is false. The absolute best way to completely destroy a ``for all'' statement is to provide a single, concrete counterexample.

---

Solutions

The problem statement is strictly false. We will disprove it by providing a counterexample.

To disprove the statement ``if $a$ divides $bc$, then $a|b$ or $a|c$'', we must find specific positive integers $a, b,$ and $c$ such that $a$ divides $bc$, but $a \nmid b$ and $a \nmid c$.

The key idea is to pick a composite number for $a$, like 4 or 6, so that its factors can be assigned to $b$ and $c$ separately. Let's try: let $a = 6$, $b = 2$, and $c = 3$.

Check the condition (the premise):

$$bc = 2 \times 3 = 6$$

Since $6$ divides $6$, the premise that $a$ divides $bc$ is satisfied.

Check the conclusion:

• Does $a$ divide $b$? No, $6$ does not divide $2$.
• Does $a$ divide $c$? No, $6$ does not divide $3$.

Since both parts of the conclusion are false, the entire statement is invalid.

Therefore, it is not true for all positive integers $a, b, c$ that $a|bc \implies a|b \text{ or } a|c$. $\blacksquare$

---

Takeaways

• Trust Your Math, Not the Paper: Examiners are human and occasionally make mistakes. If you leave a flawed question blank, you receive 0 marks. If you mathematically prove that the question is flawed, you demonstrate mastery and will be awarded marks.
• The Power of Counterexamples: To prove a universal statement (``for all $x$\ldots'') you must prove it algebraically for every number in existence. But to disprove it, you only need to find one single case where it fails.
• Euclid's Lemma: The statement in this problem becomes completely true if we add one crucial condition: $a$ must be a prime number. Composite numbers can have their factors split across $b$ and $c$, which is why $a=6$ failed above.

---

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 Inequalities