如何证明 (n^2+1) 是否被 3、5 等更多素数整除？

luyuanhong

如何证明 (n^2+1) 是否被 3、5 等更多素数整除？

原创 陈兰涛 陈词新调儿 2024 年 10 月 12 日 14:07 山东

  对于当 n 为任意整数时，你知道如何证明 (n^2+1) 是否有 3、5 这两个素数作为其素因子吗？下边我们来证明。

  先看 (n^2+1) 是否被 3 整除？

  我们改变 (n^2+1) 为 (n^2-1)+2 ，再继续变换为：(n-1)(n+1)+2 。当 n 为 3 的倍数时，可以观察到 (n^2+1) 不会被 3 整除，因为总是会余 1 。当 n 不为 3 的倍数时，因为 n 与 (n-1)、(n+1) 构成了三个连续的自然数，因此，必有一个会被 3 整除，而 n 不被 3 整除，则 (n-1) 与 (n+1) 必有一个被 3 整除，因此，(n-1)(n+1)+2 总会被 3 整除时余 2 。综上所述，则知 (n^2+1) 总不会被 3 整除。

  那能不能被 5 整除呢？这是可以的。因为末尾为 3、7 的数的平方，其末尾数总是 9 ，9+1=10 ，因此可知 (n^2+1) 的一部分可以被 5 整除。

  那能不能被 7、11、13 等更多素数整除呢？

  以 7 为例，我们可以让 n=7k+0(1、2、3、4、5、6），当 k=0 时，n=0、1、2、3、4、5、6 ，当 k=1 时，n=7、8、9、10、11、12、13 ，也就是说所有 n 均可围绕 7 建立起这种关系。则 n^2=(7k+x)^2（x 大于等于 0 且小于等于 6），展开后则得：49k^2+14kx+x^2 ，因为 49k^2+14kx 总会被 7 整除，我们只需知道 x^2+1 能否被 7 整除即可。x 分别为 0、1、2、3、4、5、6 ，则 n^2+1 分别是：1、2、5、10、17、26、37 ，可知均不被 7 整除，则知 (n^2+1) 总不会被 7 整除。其它以此类推。但这种方法太机械，当 p 很大时，需要验证更多数。因此，除非我们知道了它的素数分布。对于形如 (n^2+1) 的数列，其实只有形如 4k+1 的素数才符合其作为上述数列中的素因子存在。如 5、13、17、29.....，而 3、7、11、19、23、31.... 等则不会出现。当然，2 是特殊的素数，它也会永远出现在 (n^2+k) 的数列中，除非是开始 (2n^2+k) ，当 k 为奇数时，它永远是奇数，此时 2 就不会出现。但其它素数仍保持原有规律不变。

  在这儿，我们其实还可以得到两个重要结论：

  那就是对于 (n^2+1) 是否被 p 整除，当 p 不为 3、5 时，只需验证 [1，(p-1)/2] 中的某一个整数代入 (n^2+1) 后，是否被 p 整除，如果不被 p 整除，则可知 (n^2+1) 总不会被 p 整除。套用相似的俗语，即：要知有没有，开头就会知。当然，2、3、5 也是遵循这一原则，即对于 2 而言，每隔一个就有一个偶数，因此，前两个数还未有 2 出现，则这个数列中就不会有 2 了。对于 3 而言，只需要看 n 为 1 或 2 时，即可知，对于 5 ，只需要看 n=1、2 时即可知。或者这样说，当 n 过了 (p-1)/2 仍未出现，则说明这个素数就不可能在这个二项式中出现。

  那对于 (n^2+k) 呢？上述方法也是可以适用的，只不过是验证 x^2+k 能否被 p 整除。但只需验证 [1，(p-1)/2] 中的某一个数的方法就要调整，当 k 为素数时，对于 (n^2+k) ，则只有 n 为 k 的倍数时，(n^2+k) 才会被 k 整除，因此只验证 [1，(p-1)/2] 中的某一个数显然不准确。事实上，当 k 为素数时，k 在该二项式中的占比仅为 1/k ，即当 n 从 1 至 mk 时，在 mk 个数值中，k 会出现 m 次。但对于其它素数，如果在该二项式中出现，则会出现 2m 次。

  这也是可以证明的。比如，(n^2+k) 可被 p 整除。如果 x+y=p ，则当 (x^2+k) 被 p 整除时，那么，(y^2+k) 也会被 p 整除。这是因为 (y^2+k) 可变换为：(（p-x)^2+k) 展开后则有：(p^2-2px+x^2+k) ，(p^2-2px) 可 被 p 整除，(x^2+k) 也被 p 整除，则有 (y^2+k) 可被 p 整除。也就是说，在每一个 p 的距离内，被 p 整除的数会出现 2 次。

  这是不是很奇妙呢？在 n 的二次方构成的方程或数列中，它出现的频率除某一特定素数外，竟然占比为 2/p 。

  形如 x^2+k 的二项式，其素数分布仍是一个未解的知名数论问题。在这方面，我有了一些小成果，主要是知道了它的素数分布及这个数列中的素数个数的数量，甚至形如 mx^2+k 的形式，但离证明它，还有万里之遥。经常是一个小小的问题，之前想明白了，但再思考起来，又糊涂了。素数的问题，太绕了，其实就是上帝根本就不想让你知道它的奥秘。

陈词新调儿