2021全国高中数学联赛（A卷）加试第三题详解.pdfVIP

海纳百川，有容乃大；壁立千仞，无欲则刚。——林则徐

2021全国高中数学联赛（A卷）加试第三题详解

引言

问题

设整数证明：若，则

是合数。

分析

这是一道初等数论的题，涉及一些初等数论的常见结论，下面和

此题相关的一些知识，本文若不作特殊说明，都默认是正整数。对于

正整数，用表示的最大公约数，用表

示的最大公约数。

结论1：对于正整数，若，则

证明：令，则

证毕。

结论2：

证明：记

从而由裴蜀定理知，存在整数使得

一方面，

从而

海纳百川，有容乃大；壁立千仞，无欲则刚。——林则徐

另一方面，由结论1知

且

，从而

所以

证毕。

结论3：若是奇数，则存在某正整数使得

证明：考虑所有形如的数，它们模的余数只可能小于，

从而必然存在两个数它们模的余数是相同

的。从而

考虑到是奇数，它与互质，从而

证毕。

我们把使得成立的最小的正整数称为2模

的阶，记作

结论4：若是奇数，是正整数，若，则

若

，则存在自然数，使得

其中

，此时

海纳百川，有容乃大；壁立千仞，无欲则刚。——林则徐

从而，注意到的取值范围，这和

的最小性是矛盾的。证毕。

结论5：(欧拉定理)若

，则

其中表示

中与互质的元素个数。

证明：设

中与互质的元素为

，它们构成模的一组简系，由于互质，从而

也通过模的一组简系，从而它们的乘积模同余：

再由于与互质，从而与互质，从而两边约去

可得结论。证毕。

推论6：若是奇数，则

证明：由结论4和结论5可得。

结论7：若,则

海纳百川，有容乃大；壁立千仞，无欲则刚。——林则徐

证明：注意