この問題は、代数学続論IA第6回演習の問題です。内容は以下の通りです。 * 問1: $p=11$ を法として、 * (1) $2, 3, ..., p-2 \pmod{p}$ を掛け合わせて $1 \pmod{p}$ となる二つの合同類の組に分ける。 * (2) (1)の結果を利用して、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$ について、$ai \pmod{p}$ を求める。 * (2) この場合に、Fermatの小定理の証明をたどり、$a^{p-1} \equiv 1 \pmod{p}$ となることを確かめる。

はい、数学の問題を解きます。

1. 問題の内容

この問題は、代数学続論IA第6回演習の問題です。内容は以下の通りです。

* 問1: $p=11$ を法として、

* (1) $2, 3, ..., p-2 \pmod{p}$ を掛け合わせて $1 \pmod{p}$ となる二つの合同類の組に分ける。

* (2) (1)の結果を利用して、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$ について、$ai \pmod{p}$ を求める。

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

2. 解き方の手順

問1

(1) $p = 11$ なので、 $2, 3, ..., 9$ を考えます。

$2 \times 6 \equiv 12 \equiv 1 \pmod{11}$

$3 \times 4 \equiv 12 \equiv 1 \pmod{11}$

$5 \times 9 \equiv 45 \equiv 1 \pmod{11}$

$7 \times 8 \equiv 56 \equiv 1 \pmod{11}$

よって、組は $(2, 6), (3, 4), (5, 9), (7, 8)$ となります。

(2) $(p-1)! = 10! = 1 \times 2 \times 3 \times ... \times 10 \pmod{11}$

(1)より、$2 \times 3 \times 4 \times 5 \times 6 \times 7 \times 8 \times 9 \equiv 1 \pmod{11}$

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

したがって、Wilsonの定理 $(p-1)! \equiv -1 \pmod{p}$ が成り立ちます。

問2

(1) 21を2進展開すると、$21 = 16 + 4 + 1 = 2^4 + 2^2 + 2^0$ となるので、$21 = (10101)_2$です。

(2)

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

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

$7^{2^3} = 7^8 = (7^4)^2 = 2401^2 = 5764801$

$7^{2^4} = 7^{16} = (7^8)^2 = 5764801^2 = 33232930569601$

(3) $7^{21} \pmod{43}$ を計算します。

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

$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 1296 - 43 \times 30 = 1296 - 1290 \equiv 6 \pmod{43}$

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

よって、$7^{21} \equiv 36 \times 36 \times 7 \equiv 6 \times 36 \times 7 \equiv 36 \times 36 \times 7 \equiv 1296 \times 7 \equiv 6 \times 7 \equiv 42 \equiv -1 \pmod{43}$

(4) $7^{42} \pmod{43}$ を計算します。

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

問3

(1) $p = 7, a = 3$ なので、

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

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

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

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

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

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

(2) $a^{p-1} = 3^{7-1} = 3^6 \pmod{7}$

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

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

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

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

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

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

よって、$3^{6} \equiv 1 \pmod{7}$

3. 最終的な答え

問1

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

(2) Wilsonの定理は成り立つ。

問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, 6, 2, 5, 1, 4 \pmod{7}$

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