フェルマーの小定理とオイラーの定理 | 初等整数論

1 フェルマーの小定理

定理 1.1. $p$ を素数、 $a$ を $p\nmid a$ を満たす整数とすると、

a^{p-1}\equiv1\pmod p

が成り立つ。

証明. $1\le i,j\le p-1$ を満たす整数 $i,j$ を取る。 $p\nmid i$ かつ $p\nmid a$ なので、§A4.2 補題 2.1により $p\nmid ia$ である。したがって $ia$ の法 $p$ における余りは $1,2,\ldots,p-1$ のいずれかである。 $ia\equiv ja\pmod p$ ならば $p\mid(i-j)a$ であり、同じ補題と $p\nmid a$ から $p\mid i-j$ を得る。 $1\le i,j\le p-1$ なので $|i-j|<p$ であり、 $i=j$ となる。よって $a,2a,\ldots,(p-1)a$ の余りは互いに異なり、 $1,2,\ldots,p-1$ の並べ替えになる。

両方の積を取ると

(p-1)!\,a^{p-1}\equiv(p-1)!\pmod p

を得る。§A4.2 補題 2.1を繰り返し用いると、 $p$ は $(p-1)!$ を割り切らないので、 $\gcd((p-1)!,p)=1$ である。したがって§A4.5 命題 3.2により $(p-1)!$ を消去して、 $a^{p-1}\equiv1\pmod p$ を得る。▨

2 オイラーの定理

法が合成数の場合には、法と互いに素な整数を用いて、フェルマーの小定理の証明と同じ議論を行います。

定義 2.1 (既約剰余系). 整数 $n\ge2$ に対し、 $n$ と互いに素な剰余類から代表を一つずつ選んだ組を、法 $n$ の既約剰余系 (reduced residue system) という。

$1$ 以上 $n$ 以下で $n$ と互いに素な整数の全体は、法 $n$ の既約剰余系です。その個数を $\varphi(n)$ と書きます。

定理 2.2. $n\ge2$ を整数、 $a$ を $\gcd(a,n)=1$ を満たす整数とすると、

a^{\varphi(n)}\equiv1\pmod n

が成り立つ。

証明. $1$ 以上 $n$ 以下で $n$ と互いに素な整数を $r_1,\ldots,r_{\varphi(n)}$ とする。各 $ar_i$ は $n$ と互いに素である。実際、 $n$ と $ar_i$ に共通する素因数があれば、§A4.2 補題 2.1により、その素数は $a,r_i$ のどちらかを割り切り、 $\gcd(a,n)=\gcd(r_i,n)=1$ に反する。 $ar_i$ の法 $n$ における余りも $n$ と互いに素であるので、その余りは $r_1,\ldots,r_{\varphi(n)}$ のいずれかに等しい。 $ar_i\equiv ar_j\pmod n$ ならば、 $\gcd(a,n)=1$ と§A4.5 命題 3.2によって $a$ を消去して $r_i\equiv r_j\pmod n$ を得る。 $r_i,r_j$ は $1$ 以上 $n$ 以下なので $|r_i-r_j|<n$ であり、 $r_i=r_j$ となる。したがって、 $ar_1,\ldots,ar_{\varphi(n)}$ の余りは $r_1,\ldots,r_{\varphi(n)}$ の並べ替えになる。

$R=r_1\cdots r_{\varphi(n)}$ とおく。両方の積を取ると

a^{\varphi(n)}R\equiv R\pmod n

を得る。各 $r_i$ は $n$ と互いに素なので、§A4.2 補題 2.1を繰り返し用いると、 $n$ のどの素因数も $R$ を割り切らない。よって $\gcd(R,n)=1$ であり、§A4.5 命題 3.2により $R$ を消去して $a^{\varphi(n)}\equiv1\pmod n$ を得る。▨

注意 2.3. 法 $1$ では、任意の二整数の差が $1$ で割り切れるので、すべての整数は互いに合同である。 $\varphi(1)=1$ であり、任意の整数 $a$ に対して $a^{\varphi(1)}\equiv1\pmod1$ が成り立つ。

素数 $p$ に対しては $\varphi(p)=p-1$ なので、フェルマーの小定理はオイラーの定理の特別な場合です。

3 累乗の周期と指数の縮約

命題 3.1. $n\ge2$ を整数、 $a$ を $\gcd(a,n)=1$ を満たす整数とする。任意の非負整数 $k$ に対して

a^{k+\varphi(n)}\equiv a^k\pmod n

が成り立つ。また、非負整数 $m$ を $\varphi(n)$ で割った余りを $r$ とすると、

a^m\equiv a^r\pmod n

が成り立つ。

証明.定理 2.2により $a^{\varphi(n)}\equiv1\pmod n$ である。両辺に $a^k$ を掛けると、最初の合同式を得る。 $m=q\varphi(n)+r$ 、 $q\ge0$ 、 $0\le r<\varphi(n)$ と書くと、

a^m=(a^{\varphi(n)})^qa^r\equiv a^r\pmod n

である。▨

注意 3.2. $\varphi(n)$ は累乗の余りの周期の一つであり、最小の正の周期とは限らない。例えば $a=1,n=5$ なら、すべての非負整数 $k$ に対して $1^k\equiv1\pmod5$ なので、最小の正の周期は $1$ であるが、 $\varphi(5)=4$ である。

例 3.3. $3^{100}$ を $7$ で割った余りを求める。 $7$ は素数で $7\nmid3$ なので、定理 1.1より $3^6\equiv1\pmod7$ である。 $100=6\cdot16+4$ より

3^{100}\equiv(3^6)^{16}3^4\equiv3^4\pmod7

となる。 $3^1\equiv3$ 、 $3^2\equiv2$ 、 $3^3\equiv6$ 、 $3^4\equiv4\pmod7$ なので、求める余りは $4$ である。

問題 3.4. $2^{1000}$ を $100$ で割った余りを求めよ。

解答.

$\gcd(2,100)=2$ なので、法 $100$ にオイラーの定理を直接適用することはできない。 $100=4\cdot25$ と分ける。 $1000\ge2$ なので、 $2^{1000}\equiv0\pmod4$ である。 $1$ 以上 $25$ 以下で $25$ と互いに素でない整数は $5,10,15,20,25$ の五つなので、 $\varphi(25)=20$ である。 $\gcd(2,25)=1$ だから、定理 2.2より $2^{20}\equiv1\pmod{25}$ であり、

2^{1000}=(2^{20})^{50}\equiv1\pmod{25}

となる。

求める余りを $r$ とすると、 $r\equiv1\pmod{25}$ より $r=1+25t$ と書くことができる。法 $4$ では $0\equiv1+t$ なので、 $t\equiv3\pmod4$ となる。したがって $r\equiv76\pmod{100}$ であり、 $0\le r<100$ より、求める余りは $76$ である。 $4$ と $25$ は互いに素なので、§A4.6 補題 2.1によって、二つの余りの条件を満たす剰余類は法 $100$ でただ一つである。▨

4 擬素数と合成数判定

定義 4.1 (擬素数とカーマイケル数). $a$ を整数とする。合成数 $n$ が $\gcd(a,n)=1$ かつ $a^{n-1}\equiv1\pmod n$ を満たすとき、 $n$ を底 $a$ の擬素数 (pseudoprime) という。任意の整数 $a$ について、 $\gcd(a,n)=1$ ならば $a^{n-1}\equiv1\pmod n$ となる合成数 $n$ を、カーマイケル数 (Carmichael number) という。

例 4.2. $341=11\cdot31$ は合成数であるが、 $2^{10}=1024=3\cdot341+1$ なので、

2^{340}=(2^{10})^{34}\equiv1\pmod{341}

となる。したがって $341$ は底 $2$ の擬素数であり、フェルマーの小定理の逆は成り立たない。

例 4.3. $561=3\cdot11\cdot17$ はカーマイケル数である。実際、 $\gcd(a,561)=1$ を満たす整数 $a$ を取ると、 $a$ は $3,11,17$ のいずれでも割り切れない。定理 1.1により、 $a^2\equiv1\pmod3$ 、 $a^{10}\equiv1\pmod{11}$ 、 $a^{16}\equiv1\pmod{17}$ である。 $2,10,16$ はすべて $560$ を割り切るので、 $a^{560}-1$ は $3,11,17$ のそれぞれで割り切れる。相異なる素因数の積も $a^{560}-1$ を割り切るので、 $a^{560}\equiv1\pmod{561}$ となる。

命題 4.4. 整数 $n\ge2$ に対して、 $\gcd(a,n)=1$ かつ $a^{n-1}\not\equiv1\pmod n$ を満たす整数 $a$ が存在すれば、 $n$ は合成数である。

証明. $n$ が素数であれば、 $\gcd(a,n)=1$ から $n\nmid a$ となり、定理 1.1により $a^{n-1}\equiv1\pmod n$ となる。したがって、仮定を満たす $a$ が存在するとき、 $n$ は素数ではない。 $n\ge2$ なので、 $n$ は合成数である。▨

$n$ と互いに素な底 $a$ を選び、 $a^{n-1}$ の余りを調べる方法をフェルマーテストといいます。余りが $1$ でなければ $n$ を合成数と判定することができますが、余りが $1$ でも $n$ を素数と確定することはできません。フェルマーテストは、ミラー–ラビン法などの確率的素数判定法の出発点となる方法です。

閑話休題：フェルマーとオイラーの証明史 フェルマーは1640年のフレニクル・ド・ベシー宛の手紙で小定理を述べ、証明が長いため送らないと記したと伝えられています。小定理の最初の公刊された証明はオイラーによるもので、原論文は1736年に執筆され、1741年に公刊されました（Euler Archive の書誌と原論文）。フェルマーの最終定理についても、フェルマー自身は証明を残していません。この定理の証明は、1995年にワイルズによって公刊されました。

5 例題

レベル2 — フェルマーの小定理とオイラーの定理

次のべき乗を、指定された法で計算せよ（フェルマーの小定理・オイラーの定理で指数を落とすこと）。

解法の型 $gcd(a,n)=1$ のとき $a^\phi(n)$ $\equiv$ 1 (mod n)（n が素数 p なら a^(p−1) $\equiv$ 1）。指数を $\phi(n)$ で割った余りに落とす

例 5.1. 4^54 を 11 で割った余りを求めよ。

4^{54} \bmod 11

答 $3$

注意 11 は素数で 11 は 4 を割り切らないから、フェルマーの小定理より 4^10 $\equiv$ 1 (mod 11)。54 $=$ 10×5 + 4 なので 4^54 $\equiv$ (4^10)^5 · 4^4 $\equiv$ 4^4 (mod 11)。4^4 $=$ 256 を 11 で割った余りは 3。指数がどれだけ大きくても、法より 1 小さい 10 で割った余りだけ見ればよい、というのが定理の使い方。

例 5.2. 5^355 を 23 で割った余りを求めよ。

5^{355} \bmod 23

答 $10$

注意 23 は素数で 23 は 5 を割り切らないから、フェルマーの小定理より 5^22 $\equiv$ 1 (mod 23)。355 $=$ 22×16 + 3 なので 5^355 $\equiv$ (5^22)^16 · 5^3 $\equiv$ 5^3 (mod 23)。5^3 $=$ 125 を 23 で割った余りは 10。指数がどれだけ大きくても、法より 1 小さい 22 で割った余りだけ見ればよい、というのが定理の使い方。

例 5.3. 3^130 を 7 で割った余りを求めよ。

3^{130} \bmod 7

答 $4$

注意 7 は素数で 7 は 3 を割り切らないから、フェルマーの小定理より 3^6 $\equiv$ 1 (mod 7)。130 $=$ 6×21 + 4 なので 3^130 $\equiv$ (3^6)^21 · 3^4 $\equiv$ 3^4 (mod 7)。3^4 $=$ 81 を 7 で割った余りは 4。指数がどれだけ大きくても、法より 1 小さい 6 で割った余りだけ見ればよい、というのが定理の使い方。

例 5.4. 5^178 を 17 で割った余りを求めよ。

5^{178} \bmod 17

答 $8$

注意 17 は素数で 17 は 5 を割り切らないから、フェルマーの小定理より 5^16 $\equiv$ 1 (mod 17)。178 $=$ 16×11 + 2 なので 5^178 $\equiv$ (5^16)^11 · 5^2 $\equiv$ 5^2 (mod 17)。5^2 $=$ 25 を 17 で割った余りは 8。指数がどれだけ大きくても、法より 1 小さい 16 で割った余りだけ見ればよい、というのが定理の使い方。

例 5.5. 4^110 を 7 で割った余りを求めよ。

4^{110} \bmod 7

答 $2$

注意 7 は素数で 7 は 4 を割り切らないから、フェルマーの小定理より 4^6 $\equiv$ 1 (mod 7)。110 $=$ 6×18 + 2 なので 4^110 $\equiv$ (4^6)^18 · 4^2 $\equiv$ 4^2 (mod 7)。4^2 $=$ 16 を 7 で割った余りは 2。指数がどれだけ大きくても、法より 1 小さい 6 で割った余りだけ見ればよい、というのが定理の使い方。

例 5.6. 9^332 を 23 で割った余りを求めよ。

9^{332} \bmod 23

答 $12$

注意 23 は素数で 23 は 9 を割り切らないから、フェルマーの小定理より 9^22 $\equiv$ 1 (mod 23)。332 $=$ 22×15 + 2 なので 9^332 $\equiv$ (9^22)^15 · 9^2 $\equiv$ 9^2 (mod 23)。9^2 $=$ 81 を 23 で割った余りは 12。指数がどれだけ大きくても、法より 1 小さい 22 で割った余りだけ見ればよい、というのが定理の使い方。

例 5.7. 8^196 を 17 で割った余りを求めよ。

8^{196} \bmod 17

答 $16$

注意 17 は素数で 17 は 8 を割り切らないから、フェルマーの小定理より 8^16 $\equiv$ 1 (mod 17)。196 $=$ 16×12 + 4 なので 8^196 $\equiv$ (8^16)^12 · 8^4 $\equiv$ 8^4 (mod 17)。8^4 $=$ 4096 を 17 で割った余りは 16。指数がどれだけ大きくても、法より 1 小さい 16 で割った余りだけ見ればよい、というのが定理の使い方。

例 5.8. 5^137 を 21 で割った余りを求めよ。

5^{137} \bmod 21

答 $17$

注意 gcd(5, 21) $=$ 1 で $\phi(21) =$ 12 だから、オイラーの定理より 5^12 $\equiv$ 1 (mod 21)。137 $=$ 12×11 + 5 なので 5^137 $\equiv$ (5^12)^11 · 5^5 $\equiv$ 5^5 (mod 21)。5^5 $=$ 3125 を 21 で割った余りは 17。指数がどれだけ大きくても、 $\phi(21) =$ 12 で割った余りだけ見ればよい、というのが定理の使い方。

例 5.9. 8^111 を 13 で割った余りを求めよ。

8^{111} \bmod 13

答 $5$

注意 13 は素数で 13 は 8 を割り切らないから、フェルマーの小定理より 8^12 $\equiv$ 1 (mod 13)。111 $=$ 12×9 + 3 なので 8^111 $\equiv$ (8^12)^9 · 8^3 $\equiv$ 8^3 (mod 13)。8^3 $=$ 512 を 13 で割った余りは 5。指数がどれだけ大きくても、法より 1 小さい 12 で割った余りだけ見ればよい、というのが定理の使い方。

例 5.10. 3^360 を 35 で割った余りを求めよ。

3^{360} \bmod 35

答 $1$

注意 gcd(3, 35) $=$ 1 で $\phi(35) =$ 24 だから、オイラーの定理より 3^24 $\equiv$ 1 (mod 35)。360 $=$ 24×15 はちょうど 24 の倍数なので 3^360 $\equiv$ (3^24)^15 $\equiv$ 1 (mod 35)。指数がどれだけ大きくても、 $\phi(35) =$ 24 で割った余りだけ見ればよい、というのが定理の使い方。

6 演習

レベル2 — フェルマーの小定理とオイラーの定理

次のべき乗を、指定された法で計算せよ（フェルマーの小定理・オイラーの定理で指数を落とすこと）。

解法の型 $gcd(a,n)=1$ のとき $a^\phi(n)$ $\equiv$ 1 (mod n)（n が素数 p なら a^(p−1) $\equiv$ 1）。指数を $\phi(n)$ で割った余りに落とす

問題 6.1. 2^95 を 19 で割った余りを求めよ。

2^{95} \bmod 19

解答.

答 $13$

注意 19 は素数で 19 は 2 を割り切らないから、フェルマーの小定理より 2^18 $\equiv$ 1 (mod 19)。95 $=$ 18×5 + 5 なので 2^95 $\equiv$ (2^18)^5 · 2^5 $\equiv$ 2^5 (mod 19)。2^5 $=$ 32 を 19 で割った余りは 13。指数がどれだけ大きくても、法より 1 小さい 18 で割った余りだけ見ればよい、というのが定理の使い方。▨

問題 6.2. 7^320 を 25 で割った余りを求めよ。

7^{320} \bmod 25

解答.

答 $1$

注意 gcd(7, 25) $=$ 1 で $\phi(25) =$ 20 だから、オイラーの定理より 7^20 $\equiv$ 1 (mod 25)。320 $=$ 20×16 はちょうど 20 の倍数なので 7^320 $\equiv$ (7^20)^16 $\equiv$ 1 (mod 25)。指数がどれだけ大きくても、 $\phi(25) =$ 20 で割った余りだけ見ればよい、というのが定理の使い方。▨

問題 6.3. 7^82 を 10 で割った余りを求めよ。

7^{82} \bmod 10

解答.

答 $9$

注意 gcd(7, 10) $=$ 1 で $\phi(10) =$ 4 だから、オイラーの定理より 7^4 $\equiv$ 1 (mod 10)。82 $=$ 4×20 + 2 なので 7^82 $\equiv$ (7^4)^20 · 7^2 $\equiv$ 7^2 (mod 10)。7^2 $=$ 49 を 10 で割った余りは 9。指数がどれだけ大きくても、 $\phi(10) =$ 4 で割った余りだけ見ればよい、というのが定理の使い方。▨

問題 6.4. 5^154 を 7 で割った余りを求めよ。

5^{154} \bmod 7

解答.

答 $2$

注意 7 は素数で 7 は 5 を割り切らないから、フェルマーの小定理より 5^6 $\equiv$ 1 (mod 7)。154 $=$ 6×25 + 4 なので 5^154 $\equiv$ (5^6)^25 · 5^4 $\equiv$ 5^4 (mod 7)。5^4 $=$ 625 を 7 で割った余りは 2。指数がどれだけ大きくても、法より 1 小さい 6 で割った余りだけ見ればよい、というのが定理の使い方。▨

問題 6.5. 5^118 を 7 で割った余りを求めよ。

5^{118} \bmod 7

解答.

答 $2$

注意 7 は素数で 7 は 5 を割り切らないから、フェルマーの小定理より 5^6 $\equiv$ 1 (mod 7)。118 $=$ 6×19 + 4 なので 5^118 $\equiv$ (5^6)^19 · 5^4 $\equiv$ 5^4 (mod 7)。5^4 $=$ 625 を 7 で割った余りは 2。指数がどれだけ大きくても、法より 1 小さい 6 で割った余りだけ見ればよい、というのが定理の使い方。▨

問題 6.6. 5^290 を 17 で割った余りを求めよ。

5^{290} \bmod 17

解答.

答 $8$

注意 17 は素数で 17 は 5 を割り切らないから、フェルマーの小定理より 5^16 $\equiv$ 1 (mod 17)。290 $=$ 16×18 + 2 なので 5^290 $\equiv$ (5^16)^18 · 5^2 $\equiv$ 5^2 (mod 17)。5^2 $=$ 25 を 17 で割った余りは 8。指数がどれだけ大きくても、法より 1 小さい 16 で割った余りだけ見ればよい、というのが定理の使い方。▨

問題 6.7. 5^77 を 13 で割った余りを求めよ。

5^{77} \bmod 13

解答.

答 $5$

注意 13 は素数で 13 は 5 を割り切らないから、フェルマーの小定理より 5^12 $\equiv$ 1 (mod 13)。77 $=$ 12×6 + 5 なので 5^77 $\equiv$ (5^12)^6 · 5^5 $\equiv$ 5^5 (mod 13)。5^5 $=$ 3125 を 13 で割った余りは 5。指数がどれだけ大きくても、法より 1 小さい 12 で割った余りだけ見ればよい、というのが定理の使い方。▨

問題 6.8. 7^84 を 15 で割った余りを求めよ。

7^{84} \bmod 15

解答.

答 $1$

注意 gcd(7, 15) $=$ 1 で $\phi(15) =$ 8 だから、オイラーの定理より 7^8 $\equiv$ 1 (mod 15)。84 $=$ 8×10 + 4 なので 7^84 $\equiv$ (7^8)^10 · 7^4 $\equiv$ 7^4 (mod 15)。7^4 $=$ 2401 を 15 で割った余りは 1。指数がどれだけ大きくても、 $\phi(15) =$ 8 で割った余りだけ見ればよい、というのが定理の使い方。▨

問題 6.9. 2^149 を 27 で割った余りを求めよ。

2^{149} \bmod 27

解答.

答 $5$

注意 gcd(2, 27) $=$ 1 で $\phi(27) =$ 18 だから、オイラーの定理より 2^18 $\equiv$ 1 (mod 27)。149 $=$ 18×8 + 5 なので 2^149 $\equiv$ (2^18)^8 · 2^5 $\equiv$ 2^5 (mod 27)。2^5 $=$ 32 を 27 で割った余りは 5。指数がどれだけ大きくても、 $\phi(27) =$ 18 で割った余りだけ見ればよい、というのが定理の使い方。▨

問題 6.10. 2^219 を 19 で割った余りを求めよ。

2^{219} \bmod 19

解答.

答 $8$

注意 19 は素数で 19 は 2 を割り切らないから、フェルマーの小定理より 2^18 $\equiv$ 1 (mod 19)。219 $=$ 18×12 + 3 なので 2^219 $\equiv$ (2^18)^12 · 2^3 $\equiv$ 2^3 (mod 19)。2^3 $=$ 8 を 19 で割った余りは 8。指数がどれだけ大きくても、法より 1 小さい 18 で割った余りだけ見ればよい、というのが定理の使い方。▨

問題 6.11. 8^87 を 21 で割った余りを求めよ。

8^{87} \bmod 21

解答.

答 $8$

注意 gcd(8, 21) $=$ 1 で $\phi(21) =$ 12 だから、オイラーの定理より 8^12 $\equiv$ 1 (mod 21)。87 $=$ 12×7 + 3 なので 8^87 $\equiv$ (8^12)^7 · 8^3 $\equiv$ 8^3 (mod 21)。8^3 $=$ 512 を 21 で割った余りは 8。指数がどれだけ大きくても、 $\phi(21) =$ 12 で割った余りだけ見ればよい、というのが定理の使い方。▨

問題 6.12. 5^279 を 21 で割った余りを求めよ。

5^{279} \bmod 21

解答.

答 $20$

注意 gcd(5, 21) $=$ 1 で $\phi(21) =$ 12 だから、オイラーの定理より 5^12 $\equiv$ 1 (mod 21)。279 $=$ 12×23 + 3 なので 5^279 $\equiv$ (5^12)^23 · 5^3 $\equiv$ 5^3 (mod 21)。5^3 $=$ 125 を 21 で割った余りは 20。指数がどれだけ大きくても、 $\phi(21) =$ 12 で割った余りだけ見ればよい、というのが定理の使い方。▨

問題 6.13. 5^274 を 17 で割った余りを求めよ。

5^{274} \bmod 17

解答.

答 $8$

注意 17 は素数で 17 は 5 を割り切らないから、フェルマーの小定理より 5^16 $\equiv$ 1 (mod 17)。274 $=$ 16×17 + 2 なので 5^274 $\equiv$ (5^16)^17 · 5^2 $\equiv$ 5^2 (mod 17)。5^2 $=$ 25 を 17 で割った余りは 8。指数がどれだけ大きくても、法より 1 小さい 16 で割った余りだけ見ればよい、というのが定理の使い方。▨

問題 6.14. 2^75 を 11 で割った余りを求めよ。

2^{75} \bmod 11

解答.

答 $10$

注意 11 は素数で 11 は 2 を割り切らないから、フェルマーの小定理より 2^10 $\equiv$ 1 (mod 11)。75 $=$ 10×7 + 5 なので 2^75 $\equiv$ (2^10)^7 · 2^5 $\equiv$ 2^5 (mod 11)。2^5 $=$ 32 を 11 で割った余りは 10。指数がどれだけ大きくても、法より 1 小さい 10 で割った余りだけ見ればよい、というのが定理の使い方。▨

問題 6.15. 4^194 を 13 で割った余りを求めよ。

4^{194} \bmod 13

解答.

答 $3$

注意 13 は素数で 13 は 4 を割り切らないから、フェルマーの小定理より 4^12 $\equiv$ 1 (mod 13)。194 $=$ 12×16 + 2 なので 4^194 $\equiv$ (4^12)^16 · 4^2 $\equiv$ 4^2 (mod 13)。4^2 $=$ 16 を 13 で割った余りは 3。指数がどれだけ大きくても、法より 1 小さい 12 で割った余りだけ見ればよい、というのが定理の使い方。▨

§A4.7フェルマーの小定理とオイラーの定理

1 フェルマーの小定理

2 オイラーの定理

3 累乗の周期と指数の縮約

4 擬素数と合成数判定

5 例題

6 演習

前提記事