素数の性質
[Ⅰ] $ab$ が $p$ の倍数ならば， $a,b$ の少なくとも一方は $p$ の倍数である。
[Ⅱ] $n^2$ が $p$ の倍数ならば， $n$ は $p$ の倍数である。
[Ⅰ] この命題の待遇をとり，
「 $a,b$ がともに $p$ の倍数でないならば， $ab$ は $p$ の倍数ではない」
ことを示す。 $q,q’,r,r’$ は整数とする。 $a,b$ がともに $p$ の倍数でないとき， $a=pq+r$ ， $b=pq’ +r’$ ( $1\leqq r \leqq -1,1 \leqq r’ \leqq p-1$ )と表せる。このとき， $ab=(pq+r)(pq’+r’)=p(pqq’+qr’+q’r)+rr’$
$1 \leqq r \leqq p-1$ ， $1 \leqq r’ \leqq p-1$ と $p$ が素数であることから， $r,r’$ の素因数分解を考えれば， $rr’$ は $p$ を素数に持たないこと，すなわち $rr’$ は $p$ の倍数ではないことが分かる。したがって， $ab$ は $p$ の倍数ではない。
よって，$ab$ が $p$ の倍数ならば， $a,b$ の少なくとも一方は $p$ の倍数である。
[Ⅱ] この命題の待遇をとり，
「 $n$ が $p$ の倍数でないならば， $n^2$ は $p$ の倍数ではない」
ことを示す。 $n$ が $p$ の倍数でないとき，整数 $q,r$ を用いて $n=pq+r$ $(1 \leqq r \leqq p-1)$ と表せ，このとき $n^2=(pq+r)^2 =p(pq^2 +2pr) +r^2$ と $p$ が素数であることから， $r$ の素因数分解を考えれば， $r^2$ は $p$ を素因数に持たないこと，すなわち $r^2$ は $p$ の倍数ではないことが分かる。したがって， $n^2$ は $p$ の倍数ではない。
よって， $n^2$ が $p$ の倍数ならば $n$ は $p$ の倍数である。
注：[Ⅱ] は， [Ⅰ] で $a=b=n$ のときである。