Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Discrete mathematics, probability and continuous mathematics / 3 / b / ii

If $p\mid a$, there is nothing to prove. Otherwise the only possible positive common divisors of the prime $p$ and $a$ show that $\gcd (p,a)=1$. By Bézout's identity, $up+va=1$ for some integers $u,v$. Multiplying by $b$ gives $b=upb+vab$. Both terms on the right are divisible by $p$, the second because $p\mid ab$. Hence $p\mid b$. This proves Euclid's lemma, including when either factor is zero or negative.