初等数的一些判定方法与整除关系

Some Determination Methods of Elementary Numbers and Divisibility Relationships

摘要: 本文探讨了初等数的质合数判定方法和整除关系，通过数学证明展示了特定函数形式的合数集、特定数字累加和的整除性质，以及质数与合数的图形规律。例如定理1、2所确定的函数形式的合数集，在初等数的质合数判别起着判定的作用，又如定理3和4、5的整除关系与寻找数形上的结合规律的证明过程中，以奇偶性质推理出的逻辑是整除关系的重要证明方法之一。所以本文工作内容为：探究和寻找一些以函数形式存在的合数集，特殊数字的n次方累加和能被特定数字整除，以数形结合探讨质合数的规律。

Abstract: This paper explores methods for distinguishing prime and composite numbers in elementary numbers and their divisibility relationships. Through mathematical proofs, it demonstrates the specific functional forms of composite number sets, the divisibility properties of the cumulative sums of specific numbers raised to powers, and the graphical patterns of prime and composite numbers. For example, the composite number sets defined by Theorems 1 and 2 play a crucial role in the distinction of prime and composite numbers in elementary numbers. Additionally, in the process of proving the divisibility relationships in Theorems 3, 4, and 5 and seeking the combined patterns of numbers and shapes, logical reasoning based on the properties of odd and even numbers is one of the important proof methods for divisibility relationships. Therefore, the work of this paper includes exploring and identifying composite number sets that exist in functional forms, investigating whether the cumulative sum of the n-th powers of special numbers can be divisible by specific numbers, and exploring the patterns of prime and composite numbers through the combination of numbers and shapes.

1. 引言

自下述两性质发现至今，许多数学家对此进行探究，也在从中找出一些规律及其判别方法，有拉托斯色尼筛选法，试除法、费马小定理、梅森素数以及哥德巴赫猜想等。这些思想也在数学(密码学、编程理论等)领域做出了大贡献。基于对质合数的判别，本文也将以已有定理出发做了些许的扩充及探究。

如试除法的思想基础源于人们对整数除法性质的基本认识，在数学发展的早期阶段，人们在研究整数的性质时，就自然地想到通过用较小的数去除以较大的数来判断其是否能整除，从而确定数的一些基本性质，这是试除法的最初雏形。17世纪，费马在研究过程中发现了关于质数和同余的这一重要规律，并于1640年提出了费马小定理，但没有给出完整证明。后来，莱布尼茨和欧拉等数学家对费马小定理进行了进一步的研究和证明，欧拉在1736年给出了费马小定理的第一个完整证明，并对其进行了推广，使其在数论中的地位更加重要，也为后来基于费马小定理的质数判定方法等奠定了理论基础。

性质1. 除了自己本身和1，没有别的约数的数叫质数。

性质2. 除了自己本身和1还有别的约数的数叫合数。

本文所述的质合数的判别方法与特定数的整除关系是由引入和探究下述引理推出而得。

引理1. 对于任意非负整数$n，f\left(n\right)=19\times 8^n+17$ 的值都是合数。

引理2. 已知质数$p\ge 5$ ，且$2p+1$ 也是质数，证明$4p+1$ 必是合数。

引理3. 已知$n\in N$ 且$4\nmid n$ ，求证：$5|\left(1^n+2^n+3^n+4^n\right)$ 。

引理4. 从1到9九个自然数中，选出六个不同的数字填在成环形的六个相邻圆圈内，使任意相邻两个圆圈内数字的和都是质数，那么最多有多少种不同的选法？(六个数字相同，排列次序不同的都算同一种)

2. 一些判别方法

通过对于引理1的探究和扩充推出此合数集定理。

定理1. 对于任意非负整数$n$ ，

$f\left(n\right)=9^{n}a+b$ (其中$a，b$ 为奇数)

的值均为合数。

证明：(1) 当$n=4k\left(k\in N\right)$ 时，若$k=0$ ，则$n=0$ ，$f\left(0\right)=a+b$ ，因为$a，b$ 为奇数，有$\left(a+b\right)$ 为偶数，得到$2|f\left(0\right)$ ，此时$f\left(0\right)$ 是合数。以下设$k\ne 0$

$\begin{array}{c}f\left(n\right)=a\times 9^n+b\\ =a\times 9^{4k}+b\\ =\left(a-1\right)\times 9^{4k}+9^{4k}+b\\ =\left(a-1\right)\times 9^{4k}+{\left(80+1\right)}^{2k}+b\\ =\left(a-1\right)\times 9^{4k}+\left({80}^{2k}+C_{2k}^1\times {80}^{2k-1}+\cdots +C_{2k}^{2k-1}\times 80\right)+1+b\end{array}$

因为$\left(a-1\right)，\left(1+b\right)$ 是偶数，有$2\left|\left(a-1\right),2\right|\left(1+b\right),2|\left({80}^{2k}+C_{2k}^1\times {80}^{2k-1}+\cdots +C_{2k}^{2k-1}\times 80\right)$ ，得$2|f\left(n\right)$ ，此时$f\left(n\right)$ 是合数[1]。

(2) 当$n=4k+1\left(k\in N\right)$ 时，若$k=0$ ，则$n=1，f\left(1\right)=a\times 9+b$ ，因为$9a$ 为奇数，有$\left(9a+b\right)$ 是偶数，得到$2|f\left(1\right)$ ，此时$f\left(1\right)$ 是合数。以下设$k\ne 0$

$\begin{array}{c}f\left(n\right)=a\times 9^n+b\\ =a\times 9^{4k+1}+b\\ =9a\times 9^{4k}+b\\ =\left(9a-1\right)\times 9^{4k}+{\left(80+1\right)}^{2k}+b\\ =\left(9a-1\right)\times 9^{4k}+\left({80}^{2k}+C_{2k}^1\times {80}^{2k-1}+\cdots +C_{2k}^{2k-1}\times 80\right)+1+b\end{array}$

因为$\left(9a-1\right)，\left(1+b\right)$ 是偶数，有$2\left|\left(9a-1\right)\times 9^{4k},2\right|\left(1+b\right),2|\left({80}^{2k}+C_{2k}^1\times {80}^{2k-1}+\cdots +C_{2k}^{2k-1}\times 80\right)+1+b$ ，得到$2|f\left(n\right)$ ，此时$f\left(n\right)$ 是合数。

(3) 当$n=4k+2\left(k\in N\right)$ 时，若$k=0$ ，则$n=2，f\left(2\right)=a\times 9^2+b$ ，因为$9^{2}a$ 为奇数，有$9^{2}a+b$ 是偶数，得到$2|f\left(2\right)$ ，此时$f\left(2\right)$ 是合数。以下设$k\ne 0$

$\begin{array}{c}f\left(n\right)=a\times 9^n+b\\ =a\times 9^{4k+2}+b\\ =\left(a-1\right)\times 9^{4k+2}+{\left(80+1\right)}^{2k+1}+b\\ =\left(a-1\right)\times 9^{4k+2}+\left({80}^{2k+1}+C_{2K+1}^1\times {80}^{2K}+\cdots +C_{2K+1}^{2K}\times 80\right)+1+b\end{array}$

因为$\left(a-1\right)，\left(1+b\right)$ 为偶数，有$2\left|\left(a-1\right)\times 9^{4k+2},2\right|\left(1+b\right),2|\left({80}^{2k+1}+C_{2k+1}^1\times {80}^{2k}+\cdots +C_{2k+1}^{2k}\times 80\right)$ ，得到$2|f\left(n\right)$ ，此时$f\left(n\right)$ 是合数。

(4) 当$n=4k+3\left(k\in N\right)$ 时，若$k=0$ ，则$n=3，f\left(3\right)=a\times 9^3+b$ ，因为$9^{3}a$ 为奇数，有$9^{3}a+b$ 是偶数，得到$2|f\left(3\right)$ ，此时$f\left(3\right)$ 是合数。以下设$k\ne 0$

$\begin{array}{c}f\left(n\right)=a\times 9^n+b\\ =a\times 9^{4k+3}+b\\ =9^{3}a\times 9^{4k}+{\left(80+1\right)}^{2k}+b\\ =\left(9^{3}a-1\right)\times 9^{4k}+\left({80}^{2k}+C_{2k}^1\times {80}^{2k-1}+\cdots +C_{2k}^{2k-1}\times 80\right)+1+b\end{array}$

因为$\left(9^{3}a-1\right)，\left(1+b\right)$ 是偶数，有$2\left|\left(9^{3}a-1\right)\times 9^{4k},2\right|\left(1+b\right),2|\left({80}^{2k}+C_{2k}^1\times {80}^{2k-1}+\cdots +C_{2k}^{2k-1}\times 80\right)$ ，得到$2|f\left(n\right)$ ，此时$f\left(n\right)$ 是合数。

由以上(1)到(4)可知，对于所有非负整数$n$ ，

$f\left(n\right)=9^{n}a+b$ (其中$a，b$ 为奇数)

是合数，结论成立。

借鉴于引理2得此定理。

定理2. 质数$p\ge 5$ ，且$8p+1$ 是质数，则$4p+1$ 必是合数。

证明：因为质数$p\ge 5$ ，假设存在一个$q\left(q\in Z\right)，$ 使得$p=6q+r$ ，满足条件的余数$r$ 只能是1或5。

当$p=6q+1$ 时，$8p+1=48q+9\equiv 0\left(mod3\right)$ ，

得$3|\left(8p+1\right)$ 。与已知矛盾，可知$p$ 不是形如$6q+1$ 的数。

当$p=6q+5$ 时，$8p+1=48q+41$ 。$4p+1=24q+21\equiv 0\left(mod3\right)$ ，

得$3|\left(4p+1\right)$ [2]。

故$4p+1$ 恒为合数，结论成立。

对于引理3的推广及扩充，由此得到。

3. 整除关系

定理3. ${\displaystyle \sum }_{i=1}^n{i}^p=1+2^p+\cdots +n^p$ (其中$p$ 为正奇数)

有$\{\begin{array}{c}当n为奇数时 ， n|{\displaystyle \sum }_{i=1}^n{i}^p\\ 当n为偶数时， \frac{n}{2}|{\displaystyle \sum }_{i=1}^n{i}^p\end{array}$

证明：${\displaystyle \sum }_{i=1}^n{i}^p=1+2^p+\cdots +n^p$

$n^p\equiv 0\left(modn\right)$

${\left(n-1\right)}^p=n^p+C_p^1\times n^{p-1}\times \left(-1\right)+\cdots +C_p^{p-1}\times n\times {\left(-1\right)}^{p-1}+{\left(-1\right)}^p$

$1+{\left(n-1\right)}^p\equiv 0\left(modn\right)$

${\left(n-2\right)}^p=n^p+C_p^1\times n^{p-1}\times \left(-2\right)+\cdots +C_p^{p-1}\times n\times {\left(-2\right)}^{p-1}+{\left(-2\right)}^p$

$2^p+{\left(n-2\right)}^p\equiv 0\left(modn\right)$

$⋮$

(1) 当$n$ 为奇数时，中间数为${\left(\frac{n-1}{2}\right)}^p，{\left(n-\frac{n-1}{2}\right)}^p$

${\left(n-\frac{n-1}{2}\right)}^p=n^p+C_p^1\times n^{p-1}\times \left(-\frac{n-1}{2}\right)+\cdots +C_p^{p-1}\times n\times {\left(-\frac{n-1}{2}\right)}^{p-1}+{\left(-\frac{n-1}{2}\right)}^p$

${\left(\frac{n-1}{2}\right)}^p+{\left(n-\frac{n-1}{2}\right)}^p\equiv \left(mod n\right)$

即$1+2^p+\cdots {\left(\frac{n-1}{2}\right)}^p+{\left(n-\frac{n-1}{2}\right)}^p+\cdots +n^p\equiv 0\left(modn\right)$

$n|{\displaystyle \sum }_{i=1}^n{i}^p$

(2) 当$n$ 为偶数时，中间数为${\left(\frac{n}{2}\right)}^p$

${\left(\frac{n}{2}\right)}^p\equiv 0\left(mod\frac{n}{2}\right)$

又$\frac{n}{2}|n$

即$1+2^p+\cdots +{\left(\frac{n}{2}\right)}^p+\cdots +n^p\equiv 0\left(mod\frac{n}{2}\right)$

$\frac{n}{2}|{\displaystyle \sum }_{i=1}^n{i}^p$

得证，结论成立[3] [4]。

4. 数形上的运用

有十一个连续的自然数，它们都大于120，那么其中最多有几个质数？

解：大于120的十一个连续自然数中，最多只有连续的六个奇数，而大于120的质数必定是奇数，于是质数只可能在这六个连续的奇数之中。又因为每连续的三个奇数中至少有一个是3的倍数，现将此结论补证如下：

设连续的三个奇数依次为

$2k-1$ ，$2k+1$ ，$2k+3$

令$k=3q+r\left(0\le r\le 3\right)$

当$r=0$ 时，$3|\left(2k+3\right)$

当$r=1$ 时，$3|\left(2k+1\right)$

当$r=2$ 时，$3|\left(2k-1\right)$

所以这连续的六个奇数中最多只有四个质数[5]。

另外，在190到200这十一个连续自然数中，有191、193、197、199这四个质数。也就是说，在十一个大于120的连续自然数中，最多只能有四个质数。

从1到9九个自然数中，选出七个不相同的数字填在图1的七个圆圈内，使得任意相邻两个圆圈内数字之和都是质数，那么最多有多少种不同的选法？[6]

Figure 1. A design diagram of six circles arranged in a ring, with three of them adjacent to the central circle

图1. 成环的六个相邻圆圈与中心圆圈有三个为相邻的设计图

Figure 2. A combination where adjacent numbers consist of one odd and one even number

图2. 相邻数为一奇一偶的组合

解：1到9分别为2、4、6、8四个偶数与1、3、5、7、9五个奇数。因相邻两个数字之和都是大于2，且要满足相邻两个数之和为奇数，所以相邻的数必为一奇一偶，可假设图1中七个圆圈内填的数字分别为$a，b，c，d，x，y，z$ 。(图2) (其中$a，b，c，d$ 同奇偶，$x，y，z$ 同奇偶) [7]。

先设$a，b，c，d$ 为偶数

(1) 当$a$ 为8时，$x，y，z$ 的值只能为3、5、9，又因6不可与3、9相邻，故错误取法。

(2) 当$a$ 为6时，$x，y，z$ 的值只能为1、5、7，又因8不可与1、7相邻，故错误取法。

(3) 当$a$ 为4时，$x，y，z$ 的值只能为1、3、7、9，又因8不可与1、7相邻，6不可与3、9相邻，故错误取法。

(4) 当$a$ 为2时，$x，y，z$ 的值只能为1、3、5、9，又因8不可与1相邻，6不可与3、9相邻，5不可与4相邻，故有两种取法，分别为

再设$a，b，c，d$ 为奇数。

(5) 当$a$ 为1时，$x，y，z$ 的值只能为2、4、6，又因6不可与3、9相邻 ，5不可与4相邻，2不可与7相邻，故两种取法，分别为

(6) 当$a$ 为3时，$x，y，z$ 的值只能为2、4、8，又因8不可与1、7相邻，4不可与5相邻，2不可与7相邻，故一种取法为

(7) 当$a$ 为5时，$x，y，z$ 的值只能为2、6、8，又因8不可与1、7相邻，6不可与3，9相邻，故错误取法。

(8) 当$a$ 为7时，$x，y，z$ 的值只能为4、6，故错误取法。

(9) 当$a$ 为9时，$x，y，z$ 的值只能为2、4、8，又因8不可与1、7相邻，4不可与5相邻，2不可与7相邻，故一种取法为

2 + 2 + 1 + 1 = 6，共有6种不同的选法。

5. 总结

质合数的判别方法与整除关系中寻找其规律，是密码学中的解密与编码理论中的重要思想。因此本文主要以讨论质数的存在形式与合数的规律，发现了初等数中不同形式存在的质数，运用模运算和整除性质等方法判定，也在其以后的研究中做了证明方法的铺垫。整理所有质数的判定方法是目前数学界一大难题，因此研究与探索质数判定方法和存在形为本文章的未来目标。

项目基金

国家自然科学基金(12201335)。

NOTES

^*通讯作者。