전제 1. $ab \equiv 0 \pmod{p}$ (즉, $p$는 $ab$의 약수, $p \mid ab$)
A. $p$가 $a$의 약수 가 아니라고 가정한다.
$a$, $p$의 최대공약수 $\gcd(a, p) = g$라고 하면, 최대공약수의 정의에 따라 $g \mid p$이다.
$g$가 소수 $p$의 약수이므로, 소수의 정의에서 $g = 1$ 혹은 $g = p$이여야 한다.
$g$는 $a$의 약수인데 $g = p$라면 $p$가 $a$의 약수여야 하고, 이는 $p$가 $a$의 약수가 아니라는데에 모순이다. 따라서 $g = 1$ 이다.
베주항등식 에서 $m a + n p = 1$인 정수 $m$, $n$이 존재한다.
양변에 $b$를 곱하면 $m a b + n b p = b$이고, $p \mid ab$에서 어떤 정수 $k$에 대해 $kp = ab$ 성립, $m a b + n b p = b$에 대입하면 $m k p + n b p = b$이다.
$m k p + n b p = p (mk + nb) = b$이므로, $b$가 $p$의 배수가 된다. (= $p$는 $b$의 약수가 된다. $b \equiv 0 \pmod{p}$)
B. 같은 방법으로, $p$가 $b$의 약수가 아니라고 가정하면, $p$는 $a$의 약수가 되어버린다.