次: 演習問題 上: フェルマの小定理 前: オイラーの関数

フェルマの小定理

定理 14       $n$を正整数，$a$を$n$と互いに素な整数とする． このとき次式が成り立つ．

$$a^{\varphi(n)}\equiv 1\quad (\bmod.\ n)$$

証明     $\alpha_1,\ \alpha_2,\ \cdots,\ \alpha_m,\ m=\varphi(n)$を $n$と互いに素で，相互に$n$を法として合同でない整数とする． $a$が$n$と互いに素なので， $a\alpha_i,\ a\alpha_j$が$n$に関して合同になるのは $\alpha_i,\ \alpha_j$が合同なときにかぎる．よって $a\alpha_1,\ a\alpha_2,\ \cdots,\ a\alpha_m$は $n$と互いに素でかつ互いに合同でない整数である．

$n$と互いに素でかつ互いに合同でない整数の個数が$m$なので， $a\alpha_1,\ a\alpha_2,\ \cdots,\ a\alpha_m$のそれぞれは $\alpha_1,\ \alpha_2,\ \cdots,\ \alpha_m$のそれぞれ1つずつと $n$を法として合同である．よってその積は$n$を法として互いに合同である．

$$\begin{eqnarray*} a\alpha_1\cdot a\alpha_2\cdot \cdots \cdot a\alpha_m &=&a^m\... ...\ &\equiv& \alpha_1\cdot\cdots\cdot \alpha_m\quad (\bmod.\ n) \end{eqnarray*}$$

$\alpha_1\cdot\cdots\cdot \alpha_m$は$n$と互いに素なので，

$$a^m\equiv 1\quad (\bmod.\ n)$$

である． (証明終わり)

$n$が素数のときは $\varphi(p)=p-1$．したがって $p$と互いに素な$a$に対して

$$a^{p-1}\equiv 1\quad (\bmod.\ p)$$

である．これをフェルマの小定理という． これをそのまま入試問題としたものもある．

また，$a$が$p$と互いに素であるという条件をとり，任意の整数$a$とすると，

$$a^p\equiv a\quad (\bmod.\ p)$$

が成り立つ．