이름없는 보조정리들을 정리하기 위한 글입니다.

보조정리 0001. 밀러-라빈 소수 판별법 중
소수 $p$에 대하여 $x^{2} \equiv 1 \pmod{p}$이면 $x \equiv 1 \pmod{p}$이거나 $x \equiv -1 \pmod{p}$이다.

보조정리 증명

증명은 유클리드의 보조정리 에 의해 쉽게 할 수 있습니다.

유클리드의 보조정리
소수 $p$에 대하여 $ab \equiv 0 \pmod{p}$이면 $a \equiv 0 \pmod{p}$이거나 $b \equiv 0 \pmod{p}$이다.

$x^{2} \equiv 1 \pmod{p}$에서 $x^{2} - 1 \equiv 0 \pmod{p}$이고, $(x - 1)(x + 1) \equiv 0 \pmod{p}$이므로
$x \equiv 1 \pmod{p}$이거나 $x \equiv -1 \pmod{p}$임을 쉽게 알 수 있습니다.