Level and context: I'm a first-year undergraduate self-studying proof writing from Velleman's How to Prove It (second edition).
Exercise 17 (a). Suppose $a$, $b$, and $p$ are positive integers and $p$ is prime. Prove that if $p \mid ab$ then either $p \mid a$ or $p \mid b$. (Hint: Let $d$ be the greatest common divisor of $a$ and $p$. By exercise 16, $d = as + pt$ for some integers $s$ and $t$. Since $p$ is prime, there are not many possibilities for the value of $d$. What are they?)
And my solution so far:
Proof. Let $d$ be the greatest common divisor of $a$ and $p$. Since $p$ is prime, it has only two divisors, 1 and $p$. So we have two cases to consider.
Case 1. $d = p$. Since $d \mid a$, we have $p \mid a$.
Case 2. $d = 1$. Then $p \mid a$ is not true, so we want to show that $p \mid b$. By the division algorithm, we can choose integers $q$ and $r$ such that $b = pq + r$ and $0 \leq r < p$. To prove, $p \mid q$, we want to show that $r=0$.
Suppose $r \neq 0$.
And this where I'm stuck. We know
- $b = pq + r$ where $ 0 < r < p$
- $ 1 = as + pt$ for some integers $s$ and $t$
- $p \mid ab$, so $kp = ab$ for some integer $k$
I've tried using various substitutions to arrive at a contradiction, but failed so far.
EDIT: Following the accepted answer, the final proof is as follows:
Proof. Let $d$ be the greatest common divisor of $a$ and $p$. Since $p$ is prime, it has only two divisors, 1 and $p$. So we have two cases to consider.
Case 1. $d = p$. Since $d \mid a$, we have $p \mid a$.
Case 2. $d = 1$. By exercise 16, $1 = as + pt$ for some integers $s$ and $t$. Multiplying both sides of the equation by $b$ gives $b = abs + bpt$. Since $p \mid ab$, $kp = ab$ for some integer $k$. Then $b = kps + bpt$, so $b = p(ks + bt)$. Hence $p \mid b$. $\square$
