高中數學拓展/素數/專案/ -1 的平方根

高中數學拓展

專案 -- -1 的平方根

記號：在模算術中，如果

x^{2}\equiv y{\pmod {m}}\!

對於某些 m，那麼我們可以寫

x\equiv {\sqrt {y}}{\pmod {m}}

我們說，x 是 y 模 m 的平方根。

注意，如果 x 滿足 x² ≡ y，那麼 m - x ≡ -x 的平方也等價於 y。我們認為 x 和 -x 都是 y 的平方根。

1. 習題集中的第 5 題表明

x\equiv {\sqrt {-1}}\equiv {\sqrt {p-1}}{\pmod {p}}

存在於 p ≡ 1 (mod 4) 的素數中。解釋為什麼如果 p ≡ 3 (mod 4) 是素數，則不存在 -1 的平方根。

2. 證明對於 p ≡ 1 (mod 4) 的素數，方程

x\equiv {\sqrt {-1}}{\pmod {p}}

恰好有兩個解。

3. 假設 m 和 n 是整數，且 gcd(n,m) = 1。證明對於每個數字 0, 1, 2, 3, .... , nm - 1，都存在唯一的一對數字 a 和 b，使得滿足以下條件的最小數字 x

x ≡ a (mod m)

x ≡ b (mod n)

就是那個數字。例如，假設 m = 2，n = 3，則 4 由以下條件唯一表示

x ≡ 0 (mod 2)

x ≡ 1 (mod 3)

因為滿足上述兩個同餘式的最小 x 是 4。在這種情況下，唯一的數字對是 0 和 1。

4. 如果 p \equiv 1 (mod 4) 是素數， q \equiv 3 (mod 4) 是素數。那麼

$x\equiv {\sqrt {-1}}{\pmod {pq}}$ $x\equiv {\sqrt {-1}}{\pmod {pq}}$

是否有解？為什麼？

4. 如果 p \equiv 1 (mod 4) 是素數， q \equiv 3 (mod 4) 是素數。那麼

5. 如果 p ≡ 1 (mod 4) 是素數，q ≡ 1 (mod 4) 是素數，且 p ≠ q。證明

有 4 個解。

6. 求解

$x\equiv {\sqrt {-1}}{\pmod {493}}$ $x\equiv {\sqrt {-1}}{\pmod {493}}$

的 4 個解。

注意 493 = 17 \times 29。

7. 取一個具有兩個以上素數因子的整數 n。考慮