引言问题设整数 证明：若 ，则 是合数。 分析这是一道初等数论的题，涉及一些初等数论的常见结论，下面和此题相关的一些知识，本文若不作特殊说明，都默认是正整数。对于正整数 ，用 表示的最大公约数，用 表示的最大公约数。 结论 1：对于正整数，若 ，则 证明：令，则
证毕。 结论 2：
证明：记从而由裴蜀定理知，存在整数使得
一方面，
从而
另一方面，由结论 1 知且，从而
所以证毕。 结论 3：若是奇数，则存在某正整数使得 证明：考虑所有形如的数，它们模的余数只可能小于，从而必然存在两个数它们模的余数是相同的。从而
考虑到是奇数，它与互质，从而证毕。 我们把使得成立的最小的正整数称为 2 模的阶，记作 结论 4：若是奇数，是正整数，若，则 若，则存在自然数，使得
其中，此时
从而，注意到的取值范围，这和 的最小性是矛盾的。证毕。 结论 5：(欧拉定理) 若，则
其中表示中与互质的元素个数。 证明：设中与互质的元素为，它们构成模的一组简系，由于互质，从而也通过模的一组简系，从而它们的乘积模同余：
再由于与互质，从而与互质，从而两边约去可得结论。证毕。 推论 6：若是奇数，则 证明：由结论 4 和结论 5 可得。 结论 7：若,则 证明：注意到，再由熟知的等式
代入即可。下面给出此题的解答。 解答证明：令 若为奇数，则必为偶数，而由可知，从而是合数。 若为偶数，令，则此时必为奇数，从而令则有，由结论 4 知 若，则
其中，而由推论 6 知，从而，从而为合数。 若，那么，令，则
其中，由结论 1 知是整数，由结论 2 以及结论 7 知是整数，而由于
从而，进而
而
从而为合数。证毕。 点评这道数论题对于熟悉数论的人来说，属于中等难度，不算太难。最不易想到的是最后一种情形的构造。
|
