Fermatの小定理

同義語：フェルマーの小定理Fermat's little theorem

概要

前提知識: 素数, 合同式, 互いに素, 剰余類
Fermatの小定理は、素数 $p$ を法とする冪の合同式についての基本定理で、「$p$ で割り切れない整数を $p-1$ 乗すると、$p$ で割った余りが $1$ になる」ことを述べる。初等整数論の多くの計算（大きな冪の余り、法 $p$ での逆元、素数判定）の出発点であり、群論の Lagrangeの定理、有限体の等式 $a^q=a$、合成数を法とする Eulerの定理へと一般化される。以下、整数 $a,b$ と正の整数 $n$ について $a\equiv b\pmod n$ は $n\mid a-b$ を表す。

動機

$2$ の冪を $7$ で割った余りは $2,4,1,2,4,1,\dots$、$3$ の冪を $7$ で割った余りは $3,2,6,4,5,1,3,\dots$ と周期的に繰り返し、どちらも $6$ 乗で $1$ に戻る。$6=7-1$ である。一般に、素数 $p$ を法とすると $p$ と互いに素な整数の冪の余りは、$p-1$ 乗でかならず $1$ に戻る。これを保証するのが Fermat の小定理であり、冪の余りの計算を指数の $p-1$ による余りの計算に帰着させる。

定理

証明の鍵は、$p$ と互いに素な数を掛けても余りの集まりが並べ替わるだけだ、という次の補題である。正の整数 $n$ について、$1\le r\le n$ かつ $\gcd(r,n)=1$ を満たす整数 $r$ 全体を $R_n$ とし、その個数を $\varphi(n)$ と書く（Eulerのφ関数）。$R_n$ は法 $n$ の既約剰余系の 1 つである。

既約剰余系の並べ替え

$n$ を正の整数、$a$ を $\gcd(a,n)=1$ を満たす整数とする。各 $r\in R_n$ について $ar$ を $n$ で割った余りを $\sigma(r)$ と書くと、$\sigma(r)\in R_n$ であり（余りが $0$ のときは $n$ と読み替える）、$\sigma\colon R_n\to R_n$ は全単射である。

$r\in R_n$ とする。$\gcd(a,n)=\gcd(r,n)=1$ なので $\gcd(ar,n)=1$ である（$ar$ と $n$ の公約数となる素数があれば、Euclidの補題によりそれは $a$ か $r$ を割り、$a$ または $r$ と $n$ の公約数になってしまう）。$\sigma(r)\equiv ar\pmod n$ なので $\gcd(\sigma(r),n)=\gcd(ar,n)=1$ であり、$\sigma(r)\in R_n$ である。
$\sigma(r)=\sigma(s)$（$r,s\in R_n$）なら $n\mid a(r-s)$ である。$\gcd(a,n)=1$ なので Bézoutの等式により $ax+ny=1$ となる整数 $x,y$ があり、$r-s=(r-s)(ax+ny)=x\cdot a(r-s)+ny(r-s)$ は $n$ で割り切れる。$|r-s|< n$ なので $r=s$ である。よって $\sigma$ は単射であり、$R_n$ は有限集合なので全単射である。$\square$

Fermatの小定理

$p$ を素数、$a$ を整数とする。

$p\nmid a$ ならば $a^{p-1}\equiv1\pmod p$ である。
任意の $a$ について $a^p\equiv a\pmod p$ である。
1 と 2 は同値な主張である（HW08 Chapter VI、IR90 Chapter 3）。

剰余の並べ替えによる証明

$p$ は素数なので、$1\le r\le p-1$ の整数はすべて $p$ と互いに素であり、$R_p=\{1,2,\dots,p-1\}$ である。
1 を示す。$p\nmid a$ なら $\gcd(a,p)=1$ である。lem-fermat-little-permutation により、$a\cdot1,a\cdot2,\dots,a\cdot(p-1)$ を $p$ で割った余りは $1,2,\dots,p-1$ の並べ替えである。したがってこれらの積について
$$ \prod_{r=1}^{p-1}(ar)=a^{p-1}\,(p-1)!\equiv(p-1)!\pmod p $$
である。$(p-1)!$ は $p$ と互いに素な数の積なので $p$ と互いに素であり、$p\mid(a^{p-1}-1)(p-1)!$ と Euclidの補題から $p\mid a^{p-1}-1$ を得る。
2 を示す。$p\mid a$ なら $a^p$ も $a$ も $p$ で割り切れるので $a^p\equiv0\equiv a$ である。$p\nmid a$ なら 1 の両辺に $a$ を掛ければよい。
最後に 2 から 1 を導く。$p\nmid a$ とすると、$p\mid a^p-a=a(a^{p-1}-1)$ で $p\nmid a$ なので、Euclid の補題により $p\mid a^{p-1}-1$ である。$\square$

他の証明

同じ定理には筋の違う証明がいくつもあり、Mathpedia の他の記事がそれぞれ扱っている。

群論による証明：$(\mathbb{Z}/p\mathbb{Z})^\times$ は位数 $p-1$ の群であり、有限群の元 $g$ は $g^{|G|}=e$ を満たす（元の位数の記事の命題「元の位数と群の位数」）。これは上の証明を群の言葉で言い換えたもので、Lagrangeの定理に基づく。
二項定理による証明：$(x+y)^p\equiv x^p+y^p\pmod p$ を使って $a$ についての帰納法で $a^p\equiv a$ を示す（二項定理の記事の系「Fermat の小定理」）。
有限体による証明：位数 $q$ の有限体のすべての元は $a^q=a$ を満たす（有限体の記事の系「有限体における $x^q=x$」）。$q=p$ の場合が本定理である。

1 の仮定 $p\nmid a$ は外せない（$a=p$ なら $a^{p-1}\equiv0$）。2 はこの仮定なしに成り立つ代わりに、両辺から $a$ を割ることは $p\nmid a$ のときしかできない。

例と反例

大きな冪の余り

$3^{100}$ を $7$ で割った余りを求める。$7\nmid3$ なので $3^6\equiv1\pmod 7$ である。$100=6\cdot16+4$ なので
$$ 3^{100}=(3^6)^{16}\cdot3^4\equiv3^4=81\equiv4\pmod 7 $$
である。一般に $p\nmid a$ なら、$a^m$ の法 $p$ の余りは $m$ を $p-1$ で割った余り $r$ だけで決まり、$a^m\equiv a^r\pmod p$ である。

法 p での逆元

$p\nmid a$ なら $a\cdot a^{p-2}=a^{p-1}\equiv1\pmod p$ なので、$a^{p-2}$ は法 $p$ での $a$ の逆元である（$p=2$ なら $a^0=1$）。たとえば $p=7$、$a=3$ では $3^5=243=7\cdot34+5$ なので逆元は $5$ で、実際 $3\cdot5=15\equiv1\pmod 7$ である。この方法は Bézoutの等式の係数を求める方法（拡張 Euclid 互除法）と並ぶ、逆元の計算法である。

反例：法が素数でないとき

法を合成数 $4$、$a=3$ とすると $\gcd(3,4)=1$ だが $3^{4-1}=27\equiv3\not\equiv1\pmod 4$ であり、$a=2$ では $2^4=16\equiv0\not\equiv2\pmod 4$ である。この例は「$p$ が素数」の仮定を破り、「$n\ge2$ と $\gcd(a,n)=1$ なら $a^{n-1}\equiv1\pmod n$」「$a^n\equiv a\pmod n$」という含意をどちらも破る。合成数の法で正しいのは指数を $\varphi(n)$ にした Euler の定理（thm-fermat-little-euler）で、$\varphi(4)=2$、$3^2=9\equiv1\pmod 4$ である。

反例：逆は成り立たない

$341=11\cdot31$ は合成数だが $2^{340}\equiv1\pmod{341}$ である。実際 $2^{10}=1024=3\cdot341+1$ なので $2^{10}\equiv1\pmod{341}$、したがって $2^{340}=(2^{10})^{34}\equiv1$ である。よって「$\gcd(a,n)=1$ かつ $a^{n-1}\equiv1\pmod n$ ならば $n$ は素数である」という逆の含意は、$a=2$ で破れる。このような合成数 $n$ を底 $a$ の Fermat 擬素数（擬素数）という。
底を変えると合成数であることが分かる場合がある。$a=3$ では、$3^5=243=22\cdot11+1$ より $3^{340}=(3^5)^{68}\equiv1\pmod{11}$ だが、法 $31$ では定理により $3^{30}\equiv1$ で、$340=30\cdot11+10$ と $3^3=27\equiv-4$ から $3^{10}=(3^3)^3\cdot3\equiv(-64)\cdot3\equiv(-2)\cdot3=-6\equiv25\pmod{31}$ なので、$3^{340}\equiv25\not\equiv1\pmod{31}$ である。したがって $3^{340}\not\equiv1\pmod{341}$ であり、定理の対偶から $341$ は素数でない。

帰結と一般化

位数と素因数

$p\nmid a$ のとき、$a^m\equiv1\pmod p$ を満たす最小の正の整数 $m$ を、法 $p$ での $a$ の位数といい $\operatorname{ord}_p(a)$ と書く。定理 1 により $a^{p-1}\equiv1$ なので、このような $m$ は存在する。これは群 $(\mathbb{Z}/p\mathbb{Z})^\times$ における $a$ の類の元の位数である。

位数は p−1 を割る

$p$ を素数、$p\nmid a$ とし、$d:=\operatorname{ord}_p(a)$ とする。整数 $m\ge0$ について、$a^m\equiv1\pmod p$ であることと $d\mid m$ であることは同値である。特に $d\mid p-1$ である。

$d\mid m$ なら $m=dk$ と書けて $a^m=(a^d)^k\equiv1$ である。逆に $a^m\equiv1$ とし、除法の原理により $m=dk+r$（$0\le r< d$）と書くと、$1\equiv a^m=(a^d)^ka^r\equiv a^r\pmod p$ である。$0< r< d$ なら $d$ の最小性に反するので $r=0$、すなわち $d\mid m$ である。定理 1 により $a^{p-1}\equiv1$ なので、$d\mid p-1$ を得る。$\square$

Mersenne数の素因数

$q$ を素数とし、素数 $p$ が $2^q-1$ を割るとする。このとき $p\equiv1\pmod q$ である。$q$ が奇素数ならさらに $p\equiv1\pmod{2q}$ である。

$2^q-1$ は奇数なので $p$ は奇素数であり、$p\nmid2$ である。$2^q\equiv1\pmod p$ なので、prop-fermat-little-order により $d:=\operatorname{ord}_p(2)$ は $q$ を割る。$q$ は素数なので $d=1$ か $d=q$ であり、$d=1$ なら $2\equiv1\pmod p$ となって $p\mid1$ に反するから、$d=q$ である。同じ命題により $q\mid p-1$ である。$q$ が奇素数なら、$p-1$ は偶数で $\gcd(q,2)=1$ なので $2q\mid p-1$ である。$\square$

$q=2$ では後半は成り立たない。$2^2-1=3$ の素因数 $p=3$ は $3\equiv1\pmod2$ を満たすが、$3\not\equiv1\pmod4$ である。
たとえば $q=11$ では、$2^{11}-1=2047$ の素因数は $22k+1$ の形に限られる。$k=1$ の $23$ が実際に割り、$2047=23\cdot89$、$89=22\cdot4+1$ である。この命題は Mersenne素数の探索で、試し割りの候補を大きく減らすのに使われる。

Eulerの定理

Eulerによる一般化

$n$ を正の整数、$a$ を $\gcd(a,n)=1$ を満たす整数とすると、$a^{\varphi(n)}\equiv1\pmod n$ である。

lem-fermat-little-permutation により、$r$ が $R_n$ を動くとき $ar$ の法 $n$ の余りも $R_n$ をちょうど 1 回ずつ動く。$P:=\prod_{r\in R_n}r$ とおくと
$$ \prod_{r\in R_n}(ar)=a^{\varphi(n)}P\equiv P\pmod n $$
である。$P$ は $n$ と互いに素な数の積なので $\gcd(P,n)=1$ であり（補題の証明の最初の段落と同じ理由）、$n\mid(a^{\varphi(n)}-1)P$ から、lem-fermat-little-permutation の証明と同じく Bézout の等式を使って $n\mid a^{\varphi(n)}-1$ を得る。$\square$

$n=p$ が素数なら $\varphi(p)=p-1$ で、Fermat の小定理 1 に戻る。$n=1$ では $\varphi(1)=1$ で、法 $1$ ではすべての整数が合同なので主張は自明に成り立つ。群の言葉では、$\varphi(n)$ は単元群 $(\mathbb{Z}/n\mathbb{Z})^\times$ の位数であり、Euler の定理はこの群で $g^{|G|}=e$ となることにほかならない（Lagrangeの定理の記事の例「Eulerの定理への適用」）。

Carmichael数

ex-fermat-little-pseudoprime の $341$ は底 $3$ で見破られたが、$n$ と互いに素なすべての底 $a$ について $a^{n-1}\equiv1\pmod n$ を満たす合成数 $n$ もある。これを Carmichael 数（Carmichael数）という。次の命題は、Carmichael 数であるための十分条件を与える。

Korseltの判定条件の十分性

$n\ge2$ を、相異なる素数の積 $n=p_1p_2\cdots p_k$ として書ける整数（平方因子をもたない整数）とし、各 $i$ について $p_i-1\mid n-1$ であるとする。このとき

$\gcd(a,n)=1$ を満たす任意の整数 $a$ について $a^{n-1}\equiv1\pmod n$ である。
任意の整数 $a$ について $a^n\equiv a\pmod n$ である。

2 を先に示す。各 $i$ について $p_i\mid a^n-a$ を示す。$p_i\mid a$ なら両辺は $p_i$ で割り切れる。$p_i\nmid a$ なら、Fermat の小定理 1 により $a^{p_i-1}\equiv1\pmod{p_i}$ であり、$n-1=(p_i-1)m$ と書けるので $a^{n-1}=(a^{p_i-1})^m\equiv1$、両辺に $a$ を掛けて $a^n\equiv a\pmod{p_i}$ である。$p_1,\dots,p_k$ は相異なる素数なので対ごとに互いに素であり、それぞれが $a^n-a$ を割るから、その積 $n$ も $a^n-a$ を割る（$p_1\cdots p_{j}$ と $p_{j+1}$ が互いに素であることを使い、$j$ について帰納的に Euclid の補題を適用する）。
1 を示す。$\gcd(a,n)=1$ なら、2 により $n\mid a(a^{n-1}-1)$ であり、$\gcd(a,n)=1$ なので lem-fermat-little-permutation の証明と同じく Bézout の等式により $n\mid a^{n-1}-1$ である。$\square$

最小のCarmichael数

$561=3\cdot11\cdot17$ は相異なる素数の積で、$560=2\cdot280=10\cdot56=16\cdot35$ なので $3-1$、$11-1$、$17-1$ はすべて $560$ を割る。prop-fermat-little-korselt により、$561$ と互いに素な任意の整数 $a$ について $a^{560}\equiv1\pmod{561}$ である。$561$ は合成数なので、Fermat の小定理の条件だけでは、どの底 $a$（$\gcd(a,561)=1$）を選んでも $561$ が合成数であることは分からない。$561$ は最小の Carmichael 数であり、次は $1105=5\cdot13\cdot17$、$1729=7\cdot13\cdot19$ である（$2000$ 未満の合成数すべてについて定義を調べる有限計算で確かめられる）。

Carmichael数の特徴づけと無限性

（Korselt の判定法）合成数 $n$ が Carmichael 数であるための必要十分条件は、$n$ が平方因子をもたず、$n$ を割る各素数 $p$ について $p-1\mid n-1$ となることである。
Carmichael 数は無限に存在する。

Carmichael数についての出典

1 の十分性は prop-fermat-little-korselt で示した。必要性の証明（素数 $p$ について $p^2\mid n$ なら、法 $p^2$ の原始根を使って $a^{n-1}\not\equiv1\pmod n$ となる $a$ が作れること、および法 $p$ の原始根から $p-1\mid n-1$ が従うこと）は Kob94 Chapter V §1 に譲る。1 から、Carmichael 数は奇数で、相異なる素因数を 3 個以上もつことも従う。実際、Carmichael 数 $n$ が偶数なら、$n$ は平方因子をもたない合成数なので奇素因数 $p$ をもち、偶数 $p-1$ が奇数 $n-1$ を割ることになって矛盾する。また $n=pq$（$p< q$ は素数）なら、$q-1\mid n-1=p(q-1)+(p-1)$ から $q-1\mid p-1$ となるが、$0< p-1< q-1$ なので矛盾する。2 は Alford–Granville–Pomerance が 1994 年に証明した（AGP94）。

素数判定と一般化

Fermatテストと確率的素数判定

Fermat の小定理の対偶によると、$\gcd(a,n)=1$ で $a^{n-1}\not\equiv1\pmod n$ となる $a$ が 1 つでも見つかれば、$n$ は合成数である。冪 $a^{n-1}\bmod n$ は 2 進展開による反復 2 乗で $n$ の桁数の多項式時間で計算できるので、これは大きな数が合成数であることの高速な判定（Fermat テスト）になる。ただし Carmichael 数（ex-fermat-little-561）は $n$ と互いに素な底 $a$ をどれだけ選んでも見破れない。この欠点は、$n-1=2^st$（$t$ 奇数）と分解して $a^t,a^{2t},\dots$ を調べる Miller–Rabin テストで除かれ、奇数の合成数 $n$ に対しては、$1\le a< n$ のうちこのテストで $n$ の合成性を見逃す $a$ は高々 4 分の 1 である（Kob94 Chapter V §1）。RSA暗号では、鍵生成で大きな素数を探すのにこうした判定が使われる（Kob94 Chapter IV）。復号が正しく働くこと、すなわち相異なる素数 $p,q$ の積 $n=pq$ と、$(p-1)(q-1)$ を法として $ed\equiv1$ となる $e,d\ge1$ について、すべての整数 $m$ で $m^{ed}\equiv m\pmod n$ となることは、$n$ と互いに素でない $m$ も含めて Fermat の小定理から示せる。各素因数 $r\in\{p,q\}$ について、$r\mid m$ なら両辺は $r$ で割り切れ、$r\nmid m$ なら $ed-1$ が $r-1$ の倍数なので Fermat の小定理 1 から $m^{ed}\equiv m\pmod r$ である。$p,q$ は互いに素なので、prf-fermat-little-korselt の最後と同じく $n\mid m^{ed}-m$ となる（$\gcd(m,n)=1$ の $m$ だけなら Euler の定理から直接従う）。

群と体への一般化

Fermat の小定理と Euler の定理は、有限群 $G$ の任意の元 $g$ が $g^{|G|}=e$ を満たすこと（元の位数）の、$G=(\mathbb{Z}/p\mathbb{Z})^\times$、$(\mathbb{Z}/n\mathbb{Z})^\times$ の場合である。体の側では、位数 $q$ の有限体 $\mathbb{F}_q$ のすべての元が $a^q=a$ を満たし、$x^q-x=\prod_{a\in\mathbb{F}_q}(x-a)$ となる（有限体の記事の系「有限体における $x^q=x$」）。$q=p$ の場合の等式 $a^p=a$ は、$\mathbb{F}_p$ 上の Frobenius写像 $x\mapsto x^p$ が恒等写像であることを意味する。