In this question, a, b, and c are positive integers.
The following is an attempted proof of the false statement:
If a divides bc, then a divides b or a divides c.
['a divides bc' means 'a is a factor of bc']
Which line contains the error in this proof?
1. The statement is equivalent to 'if a does not divide b and a does not divide c then a does not divide bc'.
2. Suppose a does not divide b and a does not divide c. Then the remainder when dividing b by a is r, where 0 < r < a, and the remainder when dividing c by a is s, where 0 < s < a.
3. So b = ax + r and c = ay + s for some integers x and y.
4. Thus bc = a(axy + xs + yr) + rs.
5. So the remainder when dividing bc by a is rs.
6. Since r > 0 and s > 0, it follows that rs > 0.
7. Hence a does not divide bc.
- ALine 1
- BLine 2
- CLine 3
- DLine 4
- ELine 5
- FLine 6
Show the answer and worked solution
answer · E
- ALine 1
- BLine 2
- CLine 3
- DLine 4
- ELine 5
- FLine 6
Lines 1 to 4 are all sound: the contrapositive is stated correctly, the division algorithm gives the remainders, and the expansion of bc is right. Line 5 is where it breaks. A remainder must lie strictly below a, but rs need not: with a = 6, b = 3, c = 4 we get r = 3, s = 4 and rs = 12, which is larger than a. In fact 6 does divide 12, and this is exactly the counterexample that makes the original statement false.