# Velleman 6.4.17 - Stuck with proof involving GCD and divisibility

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

• Slight clarification: The exercise may say "Prove that if p∣ab then either p∣a or p∣b." "either C or D" is usually interpreted as "either C is true or D is true, but one of them is not true". This interpretation is incorrect. A better way to state what the author means is simply "if p | ab then ( p | a or p | b )" or "if p | ab then (at least one p | a or p | b is true". This kind of thing is why I prefer logic notation which has better defined and more universally agreed meanings. Ex. A or B is $A \vee B$. Commented Jun 11 at 7:04
• @nickalh I'm sorry, but I don't see how this comment is relevant. Have I interpreted 'C or D' as '(C or D) and not (C and D)' anywhere in the proof? And the first chapter of the book is devoted sentential logic, so by this point, readers are more than familiar with the differences of 'or' in everyday and mathematical contexts. Commented Jun 11 at 7:34
• My comment is actually about the textbook. Also, I'm just being nitpicky. Neither of my two comments are important. Commented Jun 11 at 17:16

If $$1=\gcd(a,p),$$ then there exist two integers $$c,d$$ such that $$ac+pd=1$$.
Multiply both sides by $$b$$: $$abc+pbd=b$$
$$p|abc, p|pbd \implies p|abc+pbd \implies p|b$$
You can conclude in the following way: by the division algorithm, we can choose integers $$q$$ and $$r$$ such that $$b=pq+r$$ and $$0≤r. If you multiplicate both hand sides for $$a$$ you get $$ab=pqa+ra$$, hence $$ra=ab-pqa$$, so $$p|ra$$ since $$ab$$ and $$pqa$$ are divisible by $$p$$.
Moreover, following the hint, you can get that $$1=as+pt$$ for some $$s,t$$ integers. If you multiplicate both hand sides for $$r$$ you can get $$r=ras+rpt$$ and the RHS is divisible by $$p$$ since $$p|ra$$ and $$p|rpt$$. Therefore $$p|r$$, but $$r so $$r=0$$.