高中数学扩展/素数/习题集/解答

高中数学扩展

---

补充章节 — 素数和模算术 — 逻辑

数学证明 — 集合论和无限过程 — 计数和生成函数 — 离散概率

矩阵 — 进一步的模算术 — 数学规划 — 马尔可夫链

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}}!$