[Math] If $p$ is prime and $p|ab$, then $p|a$ or $p|b$.


I am trying to understand why a line in the following proof is true. Suppose $p$ is prime and $p|ab$ where $a$ and $b$ are integers. If $p$ does not divide $a$, then $a$ and $p$ are coprime, and so there exist $x,y\in\mathbb{Z}$ such that $ax+py=1$. Then we have $abx+pby=b$ and $pby=b-abx$. Hence $p|b-abx$.

Now, the next line in the proof says that this implies that $p|b$. Why is this so?

Best Answer

$b=abx+(b-abx)$, both summands divisible by $p$.

Related Question