問題は以下の3つです。 * 問題1: $p = 11$ を法として、 $2, 3, ..., p-2 \pmod{p}$ を掛け合わせて $1 \pmod{p}$ となる二つの合同類の組に分ける。その結果を利用して、Wilsonの定理 $(p-1)! \equiv -1 \pmod{p}$ が成り立つことを確認する。 * 問題2: * (1) 21を2進展開する。 * (2) $7^{2^i}$ を $i = 1, 2, 3, 4$ について求める。 * (3) $7^{21} \pmod{43}$ を求める。 * (4) $7^{42} \pmod{43}$ を求める。 * 問題3: $p = 7, a = 3$ とする。 * (1) 各 $i = 1, 2, ..., p-1$ について、$a^i \pmod{p}$ を求める。 * (2) この場合に、Fermatの小定理の証明をたどり、$a^{p-1} \equiv 1 \pmod{p}$ となることを確認する。

1. 問題の内容

問題は以下の3つです。

* 問題1: $p = 11$ を法として、 $2, 3, ..., p-2 \pmod{p}$ を掛け合わせて $1 \pmod{p}$ となる二つの合同類の組に分ける。その結果を利用して、Wilsonの定理 $(p-1)! \equiv -1 \pmod{p}$ が成り立つことを確認する。

* 問題2:

* (1) 21を2進展開する。

* (2) $7^{2^i}$ を $i = 1, 2, 3, 4$ について求める。

* (3) $7^{21} \pmod{43}$ を求める。

* (4) $7^{42} \pmod{43}$ を求める。

* 問題3: $p = 7, a = 3$ とする。

* (1) 各 $i = 1, 2, ..., p-1$ について、$a^i \pmod{p}$ を求める。

* (2) この場合に、Fermatの小定理の証明をたどり、$a^{p-1} \equiv 1 \pmod{p}$ となることを確認する。

2. 解き方の手順

* 問題1:

* (1) $p = 11$ なので、$2, 3, ..., 9 \pmod{11}$ を考える。

$2 \times 6 \equiv 1 \pmod{11}$, $3 \times 4 \equiv 1 \pmod{11}$, $5 \times 9 \equiv 1 \pmod{11}$, $7 \times 8 \equiv 1 \pmod{11}$。

したがって、$(2, 6), (3, 4), (5, 9), (7, 8)$ がペアとなる。

* (2) $(p-1)! = 10! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 \times 8 \times 9 \times 10 \pmod{11}$

$10! \equiv 1 \times (2 \times 6) \times (3 \times 4) \times (5 \times 9) \times (7 \times 8) \times 10 \pmod{11}$

$10! \equiv 1 \times 1 \times 1 \times 1 \times 1 \times 10 \pmod{11}$

$10! \equiv 10 \pmod{11}$

$10! \equiv -1 \pmod{11}$

したがって、Wilsonの定理が成り立つ。

* 問題2:

* (1) $21 = 16 + 4 + 1 = 2^4 + 2^2 + 2^0$

よって、2進展開は $21 = (10101)_2$

* (2)

$7^{2^1} = 7^2 = 49$

$7^{2^2} = 7^4 = 49^2 = 2401$

$7^{2^3} = 7^8 = 2401^2 = 5764801$

$7^{2^4} = 7^{16} = 5764801^2 = 33232930569601$

* (3) $7^{21} \pmod{43}$

$7^1 \equiv 7 \pmod{43}$

$7^2 \equiv 49 \equiv 6 \pmod{43}$

$7^4 \equiv 6^2 \equiv 36 \pmod{43}$

$7^8 \equiv 36^2 \equiv 1296 \equiv 6 \pmod{43}$

$7^{16} \equiv 6^2 \equiv 36 \pmod{43}$

$7^{21} = 7^{16+4+1} = 7^{16} \times 7^4 \times 7^1 \pmod{43}$

$7^{21} \equiv 36 \times 36 \times 7 \pmod{43}$

$7^{21} \equiv 6 \times 7 \pmod{43}$

$7^{21} \equiv 42 \equiv -1 \pmod{43}$

* (4) $7^{42} \pmod{43}$

$7^{42} = (7^{21})^2 \pmod{43}$

$7^{42} \equiv (-1)^2 \equiv 1 \pmod{43}$

または、Fermatの小定理より $7^{42} \equiv 1 \pmod{43}$

* 問題3:

* (1) $p = 7, a = 3$

$3^1 \equiv 3 \pmod{7}$

$3^2 \equiv 9 \equiv 2 \pmod{7}$

$3^3 \equiv 3 \times 2 \equiv 6 \pmod{7}$

$3^4 \equiv 3 \times 6 \equiv 18 \equiv 4 \pmod{7}$

$3^5 \equiv 3 \times 4 \equiv 12 \equiv 5 \pmod{7}$

$3^6 \equiv 3 \times 5 \equiv 15 \equiv 1 \pmod{7}$

* (2) Fermatの小定理より、$a^{p-1} \equiv 1 \pmod{p}$

$3^{7-1} = 3^6 \equiv 1 \pmod{7}$

$3^6 = 729 = 7 \times 104 + 1$

$3^6 \equiv 1 \pmod{7}$

3. 最終的な答え

* 問題1:

* (1) $(2, 6), (3, 4), (5, 9), (7, 8)$

* (2) $(p-1)! \equiv -1 \pmod{p}$ が成り立つ

* 問題2:

* (1) $(10101)_2$

* (2) $7^{2^1} = 49$, $7^{2^2} = 2401$, $7^{2^3} = 5764801$, $7^{2^4} = 33232930569601$

* (3) $7^{21} \equiv -1 \pmod{43}$

* (4) $7^{42} \equiv 1 \pmod{43}$

* 問題3:

* (1) $3, 2, 6, 4, 5, 1$

* (2) $3^{6} \equiv 1 \pmod{7}$