[proofplan] We argue by reducing to the only non-immediate case. If $p \mid a$, the conclusion is already true; otherwise primality forces $\gcd(p,a)=1$. [Bézout's identity](/theorems/727) then gives an integer linear combination of $p$ and $a$ equal to $1$, and multiplying that identity by $b$ transfers the hypothesis $p \mid ab$ to the desired conclusion $p \mid b$. [/proofplan] [step:Reduce to the case where $p$ does not divide $a$] Assume $p \mid ab$. If $p \mid a$, then the conclusion $p \mid a$ or $p \mid b$ holds. It remains to treat the case $p \nmid a$. [/step] [step:Use primality to compute $\gcd(p,a)$] Assume $p \nmid a$. Since $p$ is prime, the positive divisors of $p$ are exactly $1$ and $p$. Any positive common divisor of $p$ and $a$ must therefore be either $1$ or $p$. The alternative $p$ is impossible because $p \nmid a$, so $\gcd(p,a)=1$. [guided] We need a Bézout identity involving $p$ and $a$, and the hypothesis needed for that identity is $\gcd(p,a)=1$. Because $p$ is prime, its only positive divisors are $1$ and $p$. Let $d \in \mathbb{Z}$ be a positive common divisor of $p$ and $a$. Since $d \mid p$, primality of $p$ gives $d=1$ or $d=p$. If $d=p$, then $p \mid a$, contradicting the case assumption $p \nmid a$. Hence every positive common divisor of $p$ and $a$ is $1$, so the greatest common divisor is \begin{align*} \gcd(p,a)=1. \end{align*} [/guided] [/step] [step:Apply Bézout's identity to $p$ and $a$] By GCD as Linear Combination, applied to the integers $p$ and $a$ with $\gcd(p,a)=1$, there exist integers $x,y \in \mathbb{Z}$ such that \begin{align*} px+ay=1. \end{align*} [/step] [step:Multiply the Bézout identity by $b$ to prove $p \mid b$] Multiplying the identity $px+ay=1$ by $b$ gives \begin{align*} pbx+aby=b. \end{align*} Since $p \mid pbx$ and $p \mid ab$ by hypothesis, also $p \mid aby$. Therefore $p$ divides the sum $pbx+aby$, so $p \mid b$. [guided] The Bézout identity expresses $1$ as an integer linear combination of $p$ and $a$: \begin{align*} px+ay=1. \end{align*} Multiplying both sides by $b$ gives \begin{align*} pbx+aby=b. \end{align*} We now check divisibility term by term. Since $pbx=p(bx)$ and $bx \in \mathbb{Z}$, we have $p \mid pbx$. By the theorem hypothesis, $p \mid ab$, so there exists $k \in \mathbb{Z}$ such that $ab=pk$. Multiplying by $y$ gives \begin{align*} aby=pky, \end{align*} and since $ky \in \mathbb{Z}$, this proves $p \mid aby$. Hence both summands $pbx$ and $aby$ are divisible by $p$, so their sum is divisible by $p$: \begin{align*} p \mid (pbx+aby). \end{align*} Using the identity $pbx+aby=b$, we conclude $p \mid b$. [/guided] [/step] [step:Conclude the disjunction] In the first case, $p \mid a$. In the remaining case, the preceding steps prove $p \mid b$. Therefore, whenever $p \mid ab$, we have $p \mid a$ or $p \mid b$. [/step]