examday

/TMUA

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$.