Misalkan \(p\) tidak membagi \(a\text{.}\) Kita harus menunjukkan bahwa \(p \mid b\text{.}\) Karena \(\gcd( a, p ) = 1\text{,}\) terdapat bilangan bulat \(r\) dan \(s\) sedemikian sehingga \(ar + ps = 1\text{.}\) Jadi,
\begin{equation*}
b = b(ar + ps) = (ab)r + p(bs)\text{.}
\end{equation*}
Karena \(p\) membagi baik \(ab\) maupun dirinya sendiri, \(p\) harus membagi \(b = (ab)r + p(bs)\text{.}\)