如何在没有计算机的情况下识别素数

170,141,183,460,469,231,731,687,303,715,884,105,727 是质数吗？在您向互联网寻求答案之前，您是否可以考虑如何在没有计算机甚至数字计算器的情况下回答该问题？

不带

1800 年代，法国数学家爱德华·卢卡斯 (Édouard Lucas) 花了数年时间证明这个 39 位数字确实是素数。他是怎么做到的？卢卡斯顺便还设计了有趣的游戏《河内塔》，他开发的方法在一个多世纪后的今天仍然有用。

河内塔

几千年来，人们一直对素数着迷。这些数字只能被 1 和它们本身整除，而其他所有整数都可以唯一地表示为几个素数的乘积；例如，15 = 3 × 5。素数本质上构成了数学元素周期表。他们还掌握着许多秘密。它们出现在数轴上有一定的规律性，但它们的出现具有尚无法量化的波动特征。这种不可预测性令专家们感到惊愕。

关于支持科学新闻

如果您喜欢这篇文章，请考虑通过订阅来支持我们屡获殊荣的新闻事业。通过购买订阅，您将有助于确保有关塑造当今世界的发现和想法的影响力故事的未来。

订阅

数学爱好者不断寻找新的素数。最大质数的当前记录（截至 2025 年 10 月）为 2136,279,841 − 1，即 41,024,320 位数字。仅大声读出这个数字就需要大约 240 天。

当前记录 ^136,279,841

具有特殊结构的素数

p ¹²⁷ 页。 ¹¹

因此，在 19 世纪中叶，卢卡斯想知道 2127 – 1 是否是素数。他面临着巨大的挑战。这个数字非常庞大，由 39 位数字组成，而当时卢卡斯显然还没有机会使用计算机。他必须手动确保 2127 – 1 没有约数（除了 1 和它本身）。

卢卡斯-莱默素数测试

s ₀ n ² _{– 1 – 2 3}