素数判定定理的延拓

唐 静，赵美利

（滁州城市职业学院，安徽滁州 239000）

众所周知，素数的判定问题一直是数论研究的中心问题之一，我们熟悉的歌德巴赫猜想、费尔玛大定理[1]，他们与素数都有直接的关系，而素数的判定方法也在不断改进。威尔逊[2]从同余角度给出了正整数P为质数的充分必要条件是，郝稚传[3]给出若P是奇数，P是素数的充分必要条件为。从组合数的角度给出了奇数是素数的判定条件，开辟了一个新的途径，在此基础上如何找到更实用、更简单、更一般的素数判断新方法仍然是数论研究的热点之一。王晓静[4]给出了组合数被素数整除的一种判别法 。针对m，n数值较大时，吴跃生[5]给出组合数被素数整除的又一种判别法。蒋娅[6]总结了能被素数整除的组合数的形式若p为素数，则，但对一个正整数是否是素数，有没有一个一般的方法均未作深入探讨。以下对奇数是素数的一般方法进行简单的探讨，并基于C++语言给出程序实现。

1 预备知识

素数的定义：一个大于1的整数，除了1和他自身外，不能被任何一个数整除，则这个数称为素数，否则就称这个数是合数，2是最小的素数。

2 相关结论

该定理给出了更一般判定奇数是质数的充要条件，我们下面给出证明，并用JAVV语言给出程序设计及实现效果。要证明此结论，需要证明以下结论。

综上所述引理4成立，由以上引理，我们容易得到定理的证明，下面我们来证明定理是正确的。

证明：“⇒”

所以定理得证。

下面我们验证此定理的正确性和简便化，比如，我们验证7是否是素数，可以取n=3，r=2，k=2，得到能够被7整除，所以7是素数。对于一个较大的正整数，如果用以前的方法和结论，会使判定步骤复杂化，比如用引理2的结论，我们将n和r的值代入，需要验证和计算的步骤比较多，用此定理，当n确定下来后，由于r，k的任意性，我们可以通过r，k的取值，把问题简单化，验证条件简单化，结果是正确的，此定理是对原来判定定理的延拓，更具有一般性。下面简单给出此定理的算法设计及分析效果。

3 算法实现及优化

下面我们用JAVV语言来实现素数的判定，具体的程序)如下:

素数的判定问题是初等数论讨论的核心问题之一，本文讨论了一种较为简单的判定方法，此方法较为简单实用；素数的求解算法问题是计算机语言中的典型问题，出现在许多计算机课程教学中，关于这些问题的研究是永无止境的课题，需要我们进一步研究和探讨。