高中數學擴充套件/素數/習題集/解答

高中數學擴充套件

內容
HSME
素數
模算術
問題和專案
習題集
專案
解答
習題解答
習題集解答
其他
定義表
完整版
PDF 版本

目前，主要精力集中在編寫每個章節的主要內容。因此，本練習解答部分可能已過時且顯得雜亂無章。

如果您有任何問題，請在“討論區”留言，或聯絡作者或主要貢獻者。

問題 1

是否存在一個規則可以確定一個三位數是否能被 11 整除？如果有，請推匯出該規則。

解答

令 x 為一個三位數，我們有

x=100a+10b+c\!

現在

x\equiv a+10b+c\equiv a-b+c{\pmod {11}}\!

我們可以得出結論，一個三位數可被 11 整除當且僅當首位和末位之和減去第二位可被 11 整除。

問題 2

證明 p，p + 2 和 p + 4 不能同時為素數。（p 為大於 3 的正整數）

解答

我們檢視模 3 運算，則 p 會落在以下三種情況之一

第一種情況

p\equiv 0{\pmod {3}}\!

我們推斷 p 不是素數，因為它能被 3 整除。

第二種情況

p\equiv 1{\pmod {3}}\!

p+2\equiv 0{\pmod {3}}\!

因此 p + 2 不是素數。

第三種情況

p\equiv 2{\pmod {3}}\!

p+4\equiv 0{\pmod {3}}\!

因此 p + 4 不是素數。

所以 p，p + 2 和 p + 4 不能同時為素數。

問題 3

求 x

{\begin{matrix}x\equiv 1^{7}+2^{7}+3^{7}+4^{7}+5^{7}+6^{7}+7^{7}\ {\pmod {7}}\\\end{matrix}}

解答

注意

-a\equiv 7-a{\pmod {7}}\!

.

然後

1^{7}\equiv (7-6)^{7}\equiv (-6)^{7}\equiv -(6^{7}){\pmod {7}}\!

.

同樣地，

2^{7}\equiv -5^{7}{\pmod {7}}\!

和

3^{7}\equiv -4^{7}{\pmod {7}}\!

.

然後

$x\!$	$\equiv 1^{7}+2^{7}+3^{7}+4^{7}+5^{7}+6^{7}+7^{7}\!$
	$\equiv 1^{7}+2^{7}+3^{7}-3^{7}-2^{7}-1^{7}+7^{7}\!$
	$\equiv 0{\pmod {7}}\!$

問題 4

9. 證明不存在整數 x 和 y 使得

x^{2}-5y^{2}=3\!

解答

將方程模 5，我們得到

x^{2}=3{\pmod {5}}\!

但是

1^{2}\equiv 1\!

2^{2}\equiv 4\!

3^{2}\equiv 4\!

4^{2}\equiv 1\!

因此不存在 a x 使得

x^{2}\equiv 3{\pmod {5}}\!

問題 5

設 p 為素數。證明

(a)

(p-1)!\equiv -1\ {\pmod {p}}

其中

n!=1\cdot 2\cdot 3\cdots (n-1)\cdot n

例如，3! = 1×2×3 = 6

(b) 因此，證明

{\sqrt {-1}}\equiv {\frac {p-1}{2}}!{\pmod {p}}

對於p ≡ 1 (mod 4)

解答

a) 如果p = 2，那麼很明顯。所以我們假設p是一個奇素數。由於p是素數，仔細思考就會發現每個不同的元素乘以另一個元素都會得到1。由於

(p-1)!=(p-1)(p-2)(p-3)\cdots 2\!

我們可以將逆元配對（兩個乘起來等於一的數字），而 (p - 1) 的逆元是它本身，因此它是唯一沒有“消去”的元素

(p-1)!\equiv (p-1)\equiv -1\!

如所要求的。

b) 從部分 a)

-1\equiv (p-1)!\!

由於p = 4k + 1，對於某個正整數k，(p - 1)! 有 4k 項

-1=1\times 2\times 3\times \cdots 2k\times (-2k)\cdots \times (-3)\times (-2)\times (-1)

右邊有偶數個減號，所以

-1=(1\times 2\times 3\times \cdots 2k)^{2}

由此可得

{\sqrt {-1}}=1\times 2\times 3\times ...2k

最後我們注意到 p = 4k + 1，我們可以得出結論

{\sqrt {-1}}={\frac {p-1}{2}}!