2つの合同方程式を解く問題です。 (2) $x^2 + 5x + 3 \equiv 0 \pmod{17}$ (3) $x^{10} \equiv 2 \pmod{17}$

1. 問題の内容

2つの合同方程式を解く問題です。

(2) $x^2 + 5x + 3 \equiv 0 \pmod{17}$

(3) $x^{10} \equiv 2 \pmod{17}$

2. 解き方の手順

(2) $x^2 + 5x + 3 \equiv 0 \pmod{17}$

平方完成します。

$x^2 + 5x \equiv -3 \pmod{17}$

$x^2 + 5x + (5/2)^2 \equiv -3 + (5/2)^2 \pmod{17}$

$x^2 + 5x + (5 \cdot 9)^2 \equiv -3 + (5 \cdot 9)^2 \pmod{17}$

$x^2 + 5x + (45)^2 \equiv -3 + (45)^2 \pmod{17}$

$x^2 + 5x + (11)^2 \equiv -3 + (11)^2 \pmod{17}$

$(x + 11)^2 \equiv -3 + 121 \pmod{17}$

$(x + 11)^2 \equiv 118 \pmod{17}$

$(x + 11)^2 \equiv 118 - 17 \cdot 6 \pmod{17}$

$(x + 11)^2 \equiv 118 - 102 \pmod{17}$

$(x + 11)^2 \equiv 16 \pmod{17}$

$x + 11 \equiv \pm 4 \pmod{17}$

$x \equiv -11 \pm 4 \pmod{17}$

$x \equiv -11 + 4 \pmod{17}$ or $x \equiv -11 - 4 \pmod{17}$

$x \equiv -7 \pmod{17}$ or $x \equiv -15 \pmod{17}$

$x \equiv 10 \pmod{17}$ or $x \equiv 2 \pmod{17}$

(3) $x^{10} \equiv 2 \pmod{17}$

$x$ は 17 を法として 2 の 10 乗根です。

原始根を探します。

2 の冪を計算します。

$2^1 \equiv 2 \pmod{17}$

$2^2 \equiv 4 \pmod{17}$

$2^3 \equiv 8 \pmod{17}$

$2^4 \equiv 16 \equiv -1 \pmod{17}$

$2^5 \equiv -2 \pmod{17}$

$2^6 \equiv -4 \pmod{17}$

$2^7 \equiv -8 \pmod{17}$

$2^8 \equiv 1 \pmod{17}$

したがって 2 は原始根ではありません。

3 の冪を計算します。

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

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

$3^3 \equiv 27 \equiv 10 \pmod{17}$

$3^4 \equiv 30 \equiv 13 \pmod{17}$

$3^5 \equiv 39 \equiv 5 \pmod{17}$

$3^6 \equiv 15 \pmod{17}$

$3^7 \equiv 45 \equiv 11 \pmod{17}$

$3^8 \equiv 33 \equiv 16 \equiv -1 \pmod{17}$

$3^{16} \equiv 1 \pmod{17}$

3 は原始根です。

$x \equiv 3^k \pmod{17}$ と書けます。

$(3^k)^{10} \equiv 2 \pmod{17}$

$3^{10k} \equiv 2 \pmod{17}$

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

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

$3^3 \equiv 10 \pmod{17}$

$3^4 \equiv 13 \pmod{17}$

$3^5 \equiv 5 \pmod{17}$

$3^6 \equiv 15 \pmod{17}$

$3^7 \equiv 11 \pmod{17}$

$3^8 \equiv 16 \pmod{17}$

$3^9 \equiv 14 \pmod{17}$

$3^{10} \equiv 8 \pmod{17}$

$3^{11} \equiv 7 \pmod{17}$

$3^{12} \equiv 4 \pmod{17}$

$3^{13} \equiv 12 \pmod{17}$

$3^{14} \equiv 2 \pmod{17}$

$3^{15} \equiv 6 \pmod{17}$

$3^{16} \equiv 1 \pmod{17}$

したがって $10k \equiv 14 \pmod{16}$

$5k \equiv 7 \pmod{8}$

$5k \equiv 7+8 \pmod{8}$

$5k \equiv 15 \pmod{8}$

$k \equiv 3 \pmod{8}$

$k = 3, 11$

$x \equiv 3^3 \equiv 10 \pmod{17}$

$x \equiv 3^{11} \equiv 7 \pmod{17}$

3. 最終的な答え

(2) $x \equiv 2, 10 \pmod{17}$

(3) $x \equiv 7, 10 \pmod{17}$