梅森素数:千年不休的探寻之旅 摘自《中国教师报》 《中国教师报》编者按:梅森索数对于许多教师来讲,是个陌 生的名词:但在近几年的高校自主招生测试中,梅森素数却频频出 现。在数千年的人类历史中,人类对梅森素数的探索脚步,也从未 停止过。人类对梅森素数的痴迷,除了因为它在密码编制、程序设 计、分布式计算技术、计算机测试等方面的实用价值外,还在于它 是人类好奇心、求知欲和荣誉感的最好见证。 4312.609 www.100math. 还记得你小学时背诵的素数表吗?那时候它还叫做质数表“2、 3、5、7…”如今你是否已经真正理解了老师说过的话:这些只能 被1和本身整除的数,具有着无穷的魅力。 还记得你中学时计算的2的整数幂吗?计算机时代,作为二进 制的体现,它们正大行其道。“2、4、8、16、32、64、128、256……” 十多年来,电脑内存的容量正是经历了这些熟悉的数字,直到现在 的2048M(2G)以及更多。 现在,让我们从这些2的整数幂中挑出以素数为指数的,再把 它减1,试试看会发现什么?22-1=3、23-1=7、23-1=31、27 -1=127……
梅森素数:千年不休的探寻之旅 摘自《中国教师报》 《 中 国 教 师 报 》 编 者 按 : 梅 森 素 数 对 于 许 多 教 师 来 讲 , 是 个 陌 生 的 名 词 ; 但 在 近 几 年 的 高 校 自 主 招 生 测 试 中 , 梅 森 素 数 却 频 频 出 现 。 在 数 千 年 的 人 类 历 史 中 , 人 类 对 梅 森 素 数 的 探 索 脚 步 , 也 从 未 停 止 过 。 人 类 对 梅 森 素 数 的 痴 迷 , 除 了 因 为 它 在 密 码 编 制 、 程 序 设 计 、 分 布 式 计 算 技 术 、 计 算 机 测 试 等 方 面 的 实 用 价 值 外 , 还 在 于 它 是 人 类 好 奇 心 、 求 知 欲 和 荣 誉 感 的 最 好 见 证 。 还 记 得 你 小 学 时 背 诵 的 素 数 表 吗 ? 那 时 候 它 还 叫 做 质 数 表 “ 2、 3、5、7„ „ ”如 今 你 是 否 已 经 真 正 理 解 了 老 师 说 过 的 话 :这 些 只 能 被 1 和 本 身 整 除 的 数 , 具 有 着 无 穷 的 魅 力 。 还 记 得 你 中 学 时 计 算 的 2 的 整 数 幂 吗 ? 计 算 机 时 代 , 作 为 二 进 制 的 体 现 ,它 们 正 大 行 其 道 。“ 2、4、8、16、32、64、128、256„„” 十 多 年 来 , 电 脑 内 存 的 容 量 正 是 经 历 了 这 些 熟 悉 的 数 字 , 直 到 现 在 的 2048M( 2G) 以 及 更 多 。 现 在 , 让 我 们 从 这 些 2 的 整 数 幂 中 挑 出 以 素 数 为 指 数 的 , 再 把 它 减 1, 试 试 看 会 发 现 什 么 ? 2 2- 1= 3、 2 3- 1= 7、 2 5- 1= 31、 2 7 - 1= 127„ „
嗯,你的心是不是激动起来了?一个伟大的发现似乎就在眼 前…… 别急别急,你的发现很妙,只是有些儿惋惜…你己经迟到了 二千年。 在2300多年前,古希腊的数学家,那位写出不朽的《几何原本》 的欧几里得在证明了素数有无穷多个之后,就顺便指出:有许多素 数可以写成2”一1的形式,其中指数P也是素数。很容易想到,刚才 你所发现的22-1、23-1、25-1、27-1正是其中排列最前的4个! 当P=11、13、17、19、23…的时候,2P-1还是素数吗?到 底有多少这种2”一1型的素数呢?在计算能力低下的公元前,这个 关于素数的探寻之旅就已经吸引了无数的人。 人们唯独对素数如此着迷不是没有理由的,它有着许多简单而 又美丽的猜想,有的已经成为定理,而有的则至今还没有答案。例 如著名的哥德巴赫猜想,让人们苦苦追索:是否任何一个大于或等 于6的素数,都可以表示为两个奇素数的和?再比如李生素数问题 所提出的:像5和7、41和43这样相差2的素数,到底有多少对呢? 在数学史上起个大早的古希腊人还有许多关于素数的发现,完 美数就是其中之一。毕达哥拉斯学派指出,如果一个数的所有因数 (包括1但不包括它本身)的和正好等于它本身,则这个数就叫做 完美数。很容易找到,6=1+2+3是第一个完美数,28=1+2+4 +7+14则是第二个完美数。他们认为,上帝用6天创造了世界, 因此6是最理想和完美的数字,而和6具有相同性质的数都堪称完 美数。 欧几里得在《几何原本》中证明了如果2”一1是一个素数,那 么2P-1(2”-1)一定是一个完美数(你会发现,当P分别等于2、 3时,它就对应着前两个完美数6、28)。 再后来,一个叫欧拉的人进一步证明,每一个偶完美数也必定 是欧几里得所给出的形式。(不要问我奇完美数呢?就连它是否存 在,本身也是无数个关于素数的难题中至今未解的一个。)
嗯 , 你 的 心 是 不 是 激 动 起 来 了 ? 一 个 伟 大 的 发 现 似 乎 就 在 眼 前„„ 别 急 别 急 , 你 的 发 现 很 妙 , 只 是 有 些 儿 惋 惜 „ „ 你 已 经 迟 到 了 二千年。 在 2300 多 年 前 ,古 希 腊 的 数 学 家 ,那 位 写 出 不 朽 的《 几 何 原 本 》 的 欧 几 里 得 在 证 明 了 素 数 有 无 穷 多 个 之 后 , 就 顺 便 指 出 : 有 许 多 素 数可以写成 2 P- 1 的 形 式 ,其 中 指 数 P 也 是 素 数 。很 容 易 想 到 ,刚 才 你所发现的 2 2- 1、2 3- 1、2 5- 1、2 7- 1 正 是 其 中 排 列 最 前 的 4 个 ! 当 P= 11、13、17、19、23„ „ 的 时 候 ,2 P- 1 还 是 素 数 吗 ? 到 底 有 多 少 这 种 2 P- 1 型 的 素 数 呢 ? 在 计 算 能 力 低 下 的 公 元 前 , 这 个 关 于 素 数 的 探 寻 之 旅 就 已 经 吸 引 了 无 数 的 人 。 人 们 唯 独 对 素 数 如 此 着 迷 不 是 没 有 理 由 的 , 它 有 着 许 多 简 单 而 又 美 丽 的 猜 想 , 有 的 已 经 成 为 定 理 , 而 有 的 则 至 今 还 没 有 答 案 。 例 如 著 名 的 哥 德 巴 赫 猜 想 , 让 人 们 苦 苦 追 索 : 是 否 任 何 一 个 大 于 或 等 于 6 的 素 数 , 都 可 以 表 示 为 两 个 奇 素 数 的 和 ? 再 比 如 孪 生 素 数 问 题 所 提 出 的 :像 5 和 7、41 和 43 这样相差 2 的 素 数 ,到 底 有 多 少 对 呢 ? 在 数 学 史 上 起 个 大 早 的 古 希 腊 人 还 有 许 多 关 于 素 数 的 发 现 , 完 美 数 就 是 其 中 之 一 。 毕 达 哥 拉 斯 学 派 指 出 , 如 果 一 个 数 的 所 有 因 数 (包括 1 但 不 包 括 它 本 身 ) 的 和 正 好 等 于 它 本 身 , 则 这 个 数 就 叫 做 完 美 数 。 很 容 易 找 到 , 6= 1+ 2+ 3 是 第 一 个 完 美 数 , 28= 1+ 2+ 4 + 7+ 14 则 是 第 二 个 完 美 数 。 他 们 认 为 , 上 帝 用 6 天 创 造 了 世 界 , 因 此 6 是 最 理 想 和 完 美 的 数 字 , 而 和 6 具 有 相 同 性 质 的 数 都 堪 称 完 美数。 欧 几 里 得 在 《 几 何 原 本 》 中 证 明 了 如 果 2 P- 1 是 一 个 素 数 , 那 么 2 P- 1( 2 P- 1) 一 定 是 一 个 完 美 数 ( 你 会 发 现 ,当 P 分别等于 2、 3 时 , 它 就 对 应 着 前 两 个 完 美 数 6、 28)。 再 后 来 , 一 个 叫 欧 拉 的 人 进 一 步 证 明 , 每 一 个 偶 完 美 数 也 必 定 是 欧 几 里 得 所 给 出 的 形 式 。( 不 要 问 我 奇 完 美 数 呢 ? 就 连 它 是 否 存 在 , 本 身 也 是 无 数 个 关 于 素 数 的 难 题 中 至 今 未 解 的 一 个 。)
很容易看到,找到了2”一1形式的素数,也就发现了新的完美 数。 形如2”一1的素数还长期占据了人们寻找到的最大素数的光荣 榜(仅在1989年后被39158×2216193-1夺走三年),因为判断这 样一个数是素数的方法比判断一个差不多大小的其他类型数是素数 的方法要简单得多。 对2”一1型素数的搜寻之旅就这样出发了,先后投入这个漫漫 长途的就有数学大师费马、笛卡尔、莱布尼兹、哥德巴赫、欧拉 高斯、哈代、图灵…这一个个闪光的名字正如暗夜前行的火炬手, 照亮了人类通往未知的道路。 历史的天空闪烁几颗星 现在,让我们坐上时间机器,回到过去,重新浏览这来路风光 吧。 1456年,又一个没有留下姓名的人发现了第5个2-1型的素 数:23-1。若是你就降生在十五世纪,或许这次发现的光荣将归属 于你。只是,你更有可能犯下和这个时代的人们一样的错误,以为 对于所有的素数P,2”一1都是素数。要知道,这个错误是一百年之 后,直到1536年,才由雷吉乌斯(Hudalricus Regius)打破的。他指 出,21-1=2047=23×89,不是素数。 不过你的莽撞完全可以得到谅解,在黑暗中寻找的数学家正如 年轻人一样,犯下的错误连上帝都会原谅。第一个对这种类型的素 数进行整理的皮特罗·卡塔尔迪(Pietro Cataldi)在他在I603年宜布 的结果中就言之凿凿地说:对于P=17,19,23,29,31和37,2 一1是素数。只可惜,37年后,他的六个结果就被推翻了两个,费 尔马使用著名的小费尔马(不是那个更著名的大费尔马定理)定理 证明了卡塔尔迪关于P=23和37的结论是错误的。 不知道下面的事实会不会让你联想到“屋漏偏逢连夜雨”呢? 大约一百年后,1738年,欧拉证明了卡塔尔迪的结果中P=29也是 错误的。幸好,欧拉又证明了P=31的结论是对的
很 容 易 看 到 , 找 到 了 2 P- 1 形 式 的 素 数 , 也 就 发 现 了 新 的 完 美 数 。 形 如 2 P- 1 的 素 数 还 长 期 占 据 了 人 们 寻 找 到 的 最 大 素 数 的 光 荣 榜 ( 仅 在 1989 年 后 被 39158×2216193- 1 夺 走 三 年 ), 因 为 判 断 这 样 一 个 数 是 素 数 的 方 法 比 判 断 一 个 差 不 多 大 小 的 其 他 类 型 数 是 素 数 的 方 法 要 简 单 得 多 。 对 2 P- 1 型 素 数 的 搜 寻 之 旅 就 这 样 出 发 了 , 先 后 投 入 这 个 漫 漫 长 途 的 就 有 数 学 大 师 费 马 、 笛 卡 尔 、 莱 布 尼 兹 、 哥 德 巴 赫 、 欧 拉 、 高 斯 、哈 代 、图 灵 „ „ 这 一 个 个 闪 光 的 名 字 正 如 暗 夜 前 行 的 火 炬 手 , 照 亮 了 人 类 通 往 未 知 的 道 路 。 历 史 的 天 空 闪 烁 几 颗 星 现 在 , 让 我 们 坐 上 时 间 机 器 , 回 到 过 去 , 重 新 浏 览 这 来 路 风 光 吧 。 1456 年 , 又 一 个 没 有 留 下 姓 名 的 人 发 现 了 第 5 个 2 P- 1 型 的 素 数 :2 1 3- 1。若 是 你 就 降 生 在 十 五 世 纪 ,或 许 这 次 发 现 的 光 荣 将 归 属 于 你 。 只 是 , 你 更 有 可 能 犯 下 和 这 个 时 代 的 人 们 一 样 的 错 误 , 以 为 对 于 所 有 的 素 数 P,2 P- 1 都 是 素 数 。要 知 道 ,这 个 错 误 是 一 百 年 之 后 , 直 到 1536 年 , 才 由 雷 吉 乌 斯 (Hudalricus Regius)打 破 的 。 他 指 出 , 2 11- 1= 2047= 23×89, 不 是 素 数 。 不 过 你 的 莽 撞 完 全 可 以 得 到 谅 解 , 在 黑 暗 中 寻 找 的 数 学 家 正 如 年 轻 人 一 样 , 犯 下 的 错 误 连 上 帝 都 会 原 谅 。 第 一 个 对 这 种 类 型 的 素 数 进 行 整 理 的 皮 特 罗 ·卡 塔 尔 迪 (Pietro Cataldi)在 他 在 1603 年宣布 的 结 果 中 就 言 之 凿 凿 地 说 : 对 于 P=17, 19, 23, 29, 31 和 37, 2 P - 1 是 素 数 。 只 可 惜 , 37 年 后 , 他 的 六 个 结 果 就 被 推 翻 了 两 个 , 费 尔 马 使 用 著 名 的 小 费 尔 马( 不 是 那 个 更 著 名 的 大 费 尔 马 定 理 )定 理 , 证 明 了 卡 塔 尔 迪 关 于 P= 23 和 37 的 结 论 是 错 误 的 。 不 知 道 下 面 的 事 实 会 不 会 让 你 联 想 到 “ 屋 漏 偏 逢 连 夜 雨 ” 呢 ? 大 约 一 百 年 后 , 1738 年 ,欧 拉 证 明 了 卡 塔 尔 迪 的 结 果 中 P= 29 也 是 错 误 的 。 幸 好 , 欧 拉 又 证 明 了 P= 31 的 结 论 是 对 的
虽然,卡塔尔迪的六个结果“阵亡”了一半,但考虑到他是用 手工计算取得结论的,而费尔马和欧拉则是使用了在他们那时最先 进的数学知识,避免了许多复杂的计算和因此可能造成的错误,因 此我们仍然要对卡塔尔迪致敬。他也由此光荣地占据了第六个和第 七个发现者之位,在他之前的,都是无名氏。 卡塔尔迪的成功,说明了整理和预测是正确道路。继他之后, 集研究成果大成的,是17世纪法国著名的数学家和修道士马林·梅 森(Marin Mersenne,.1588-1648)。 梅森热心于宗教,但更喜爱数学;他是一个交往广泛、热情诚 挚的人,更是一座“科学信息交换站”。为什么呢?那时候,学术刊 物、国际会议甚至科研机构都还没有诞生。“及时雨”般的梅森是欧 洲众多科学家之间联系的桥梁,大家把研究成果寄给他,然后再由 他转告给更多的人。费马、笛卡尔等数学家每周在他家聚会,讨论 问题,就这样慢慢形成的“梅森学院”,后来有了一个更响亮的名字 一一法兰西科学院。 1644年,梅森在欧几里得、费马等人的有关研究的基础上对2" 一1作了大量的计算、验证工作,并于1644年在他的《物理数学随 感》一书中断言:对于P=2、3、5、7、13、17、19、31、67、127、 257时,2”-1是素数:而对于P等于其他所有小于257的数时,2” -1是合数。这里前7个数(即2,3,5,7,13,17和19)是在前 人的工作中已经证实的部分。而后面的4个数(即31,67,127和
虽 然 , 卡 塔 尔 迪 的 六 个 结 果 “ 阵 亡 ” 了 一 半 , 但 考 虑 到 他 是 用 手 工 计 算 取 得 结 论 的 , 而 费 尔 马 和 欧 拉 则 是 使 用 了 在 他 们 那 时 最 先 进 的 数 学 知 识 , 避 免 了 许 多 复 杂 的 计 算 和 因 此 可 能 造 成 的 错 误 , 因 此 我 们 仍 然 要 对 卡 塔 尔 迪 致 敬 。 他 也 由 此 光 荣 地 占 据 了 第 六 个 和 第 七 个 发 现 者 之 位 , 在 他 之 前 的 , 都 是 无 名 氏 。 卡 塔 尔 迪 的 成 功 , 说 明 了 整 理 和 预 测 是 正 确 道 路 。 继 他 之 后 , 集 研 究 成 果 大 成 的 ,是 17 世 纪 法 国 著 名 的 数 学 家 和 修 道 士 马 林 ·梅 森 ( Marin Mersenne,1588– 1648)。 梅 森 热 心 于 宗 教 , 但 更 喜 爱 数 学 ; 他 是 一 个 交 往 广 泛 、 热 情 诚 挚 的 人 ,更 是 一 座“ 科 学 信 息 交 换 站 ”。为 什 么 呢 ? 那 时 候 ,学 术 刊 物 、国 际 会 议 甚 至 科 研 机 构 都 还 没 有 诞 生 。“ 及 时 雨 ”般 的 梅 森 是 欧 洲 众 多 科 学 家 之 间 联 系 的 桥 梁 , 大 家 把 研 究 成 果 寄 给 他 , 然 后 再 由 他 转 告 给 更 多 的 人 。 费 马 、 笛 卡 尔 等 数 学 家 每 周 在 他 家 聚 会 , 讨 论 问 题 ,就 这 样 慢 慢 形 成 的“ 梅 森 学 院 ”,后 来 有 了 一 个 更 响 亮 的 名 字 — — 法 兰 西 科 学 院 。 1644 年 ,梅 森 在 欧 几 里 得 、费 马 等 人 的 有 关 研 究 的 基 础 上 对 2 P - 1 作 了 大 量 的 计 算 、 验 证 工 作 , 并 于 1644 年 在 他 的 《 物 理 数 学 随 感 》一 书 中 断 言 :对 于 P= 2、3、5、7、13、17、19、31、67、127、 257 时 ,2 P- 1 是 素 数 ;而 对 于 P 等 于 其 他 所 有 小 于 257 的数时,2 P - 1 是 合 数 。这 里 前 7 个 数( 即 2,3,5,7,13,17 和 19)是 在 前 人 的 工 作 中 已 经 证 实 的 部 分 。 而 后 面 的 4 个数(即 31, 67, 127 和
257)属于被猜测的部分。不过,人们对他的断言深信不疑,连大数 学家莱布尼兹和哥德巴赫都认为它是对的。 梅森的工作极大地激发了人们研究2”一1型素数的热情,成为 素数研究的一个转折点和里程碑。为了纪念他,数学界就把这种数 称为“梅森数”,并以MP记之(其中M为梅森姓名的首字母),即 MP=2P一1。如果梅森数为素数,则称之为“梅森素数”(即2”-1型 素数)。 对梅森素数的验证,需要进行艰巨的计算,即使是“猜测”部分中 最小的M31-231-1=2147483647,也是一个10位数。而梅森自己则 承认:“一个人,使用一般的验证方法,要检验一个15位或20位的 数字是否为素数,即使终生的时间也是不够的。”年迈力衰的他四年 之后就去世了,最终并没有任何一个梅森素数的发现权归属于他, 但考虑到他已经享有了“冠名权”,就把荣誉分给那些在漫漫长途上 跋涉的发现者们吧! 那些手扛肩挑的年代 手算笔录的时代,每前进一步,都显得格外艰难。1772年,在 卡塔尔迪提出近200年之后,瑞士数学家欧拉证明了M1确实是一 个素数,这是人们找到的第8个梅森素数,它共有10位数,堪称当 时世界上已知的最大素数,欧拉也因此成为第二个在发现者名单上 留名的人。让人惊叹的是,这是在他双目失明的情况下,靠心算完 成的。这种超人般的毅力与技巧让欧拉获得了“数学英雄”的美誉。 法国大数学家拉普拉斯(P.LaPlace)说的话,或许可以代表我们的 心声:“读读欧拉,他是我们每一个人的老师。” 100年后,法国数学家鲁卡斯提出了一个用来判别MP是否是素 数的重要定理一一鲁卡斯定理,这为梅森素数的研究提供了有力的 工具。I883年,数学家波佛辛(Pervushin)利用鲁卡斯定理证明了 M1也是素数一一这是梅森漏掉了的。梅森还漏掉另外两个素数: M89和M107,它们分别在1911年与1914年被数学家鲍尔斯(Powers) 发现
257)属 于 被 猜 测 的 部 分 。不 过 ,人 们 对 他 的 断 言 深 信 不 疑 ,连 大 数 学 家 莱 布 尼 兹 和 哥 德 巴 赫 都 认 为 它 是 对 的 。 梅 森 的 工 作 极 大 地 激 发 了 人 们 研 究 2 P- 1 型 素 数 的 热 情 , 成 为 素 数 研 究 的 一 个 转 折 点 和 里 程 碑 。 为 了 纪 念 他 , 数 学 界 就 把 这 种 数 称 为 “ 梅 森 数 ”, 并 以 M P 记 之 ( 其 中 M 为 梅 森 姓 名 的 首 字 母 ), 即 M P =2P- 1。如 果 梅 森 数 为 素 数 ,则 称 之 为“ 梅 森 素 数 ”( 即 2 P- 1 型 素 数 )。 对 梅 森 素 数 的 验 证 , 需 要 进 行 艰 巨 的 计 算 , 即 使 是 “ 猜 测 ” 部 分 中 最小的 M 3 1=23 1- 1=2147483647, 也 是 一 个 10 位 数 。 而 梅 森 自 己 则 承 认 :“ 一 个 人 ,使 用 一 般 的 验 证 方 法 ,要 检 验 一 个 15 位 或 20 位 的 数 字 是 否 为 素 数 ,即 使 终 生 的 时 间 也 是 不 够 的 。”年 迈 力 衰 的 他 四 年 之 后 就 去 世 了 , 最 终 并 没 有 任 何 一 个 梅 森 素 数 的 发 现 权 归 属 于 他 , 但 考 虑 到 他 已 经 享 有 了“ 冠 名 权 ”,就 把 荣 誉 分 给 那 些 在 漫 漫 长 途 上 跋 涉 的 发 现 者 们 吧 ! 那 些 手 扛 肩 挑 的 年 代 手 算 笔 录 的 时 代 , 每 前 进 一 步 , 都 显 得 格 外 艰 难 。 1772 年,在 卡 塔 尔 迪 提 出 近 200 年 之 后 , 瑞 士 数 学 家 欧 拉 证 明 了 M 3 1 确实是一 个 素 数 ,这 是 人 们 找 到 的 第 8 个 梅 森 素 数 ,它 共 有 10 位 数 ,堪 称 当 时 世 界 上 已 知 的 最 大 素 数 , 欧 拉 也 因 此 成 为 第 二 个 在 发 现 者 名 单 上 留 名 的 人 。 让 人 惊 叹 的 是 , 这 是 在 他 双 目 失 明 的 情 况 下 , 靠 心 算 完 成 的 。这 种 超 人 般 的 毅 力 与 技 巧 让 欧 拉 获 得 了“ 数 学 英 雄 ”的 美 誉 。 法 国 大 数 学 家 拉 普 拉 斯 ( P.LaPlace) 说 的 话 , 或 许 可 以 代 表 我 们 的 心 声 :“ 读 读 欧 拉 , 他 是 我 们 每 一 个 人 的 老 师 。” 100 年 后 ,法 国 数 学 家 鲁 卡 斯 提 出 了 一 个 用 来 判 别 M P 是 否 是 素 数 的 重 要 定 理 — — 鲁 卡 斯 定 理 , 这 为 梅 森 素 数 的 研 究 提 供 了 有 力 的 工具。1883 年 , 数 学 家 波 佛 辛( Pervushin)利 用 鲁 卡 斯 定 理 证 明 了 M 6 1 也 是 素 数 — — 这 是 梅 森 漏 掉 了 的 。 梅 森 还 漏 掉 另 外 两 个 素 数 : M 8 9 和 M 1 0 7,它 们 分 别 在 1911 年 与 1914 年 被 数 学 家 鲍 尔 斯( Powers) 发现