| 查看: 64 | 回复: 0 | |||
[交流]
化核指数素因子定理
|
|
作者：阿康 定理 设 a, n ∈ ℕ⁺，p 为素数，且 (a, p) = 1。若 p − 1 ∣ 2(n − 1) 则 p 必整除 aⁿ⁻¹ − 1 或 aⁿ⁻¹ + 1。 即：所有满足该条件的素数 p，无一遗漏地全部存在于 aⁿ⁻¹ − 1 和 aⁿ⁻¹ + 1 的素因子之并集中。 证明 令 m = n − 1，由条件设 2m = k(p − 1)。 由费马小定理（(a, p) = 1）： aᵖ⁻¹ ≡ 1 (mod p) ⟹ a²ᵐ = aᵏ⁽ᵖ⁻¹⁾ ≡ 1 (mod p) 所以： p ∣ a²ᵐ − 1 = (aᵐ − 1)(aᵐ + 1) 因 p 为素数，必整除至少一个因子，故 aⁿ⁻¹ ≡ ±1 (mod p)。证毕。 验证举例（展示”所有”性） 取 n = 61，则 m = 60，条件化为 p − 1 ∣ 120。 列出 120 的所有正因子 d，若 d + 1 为素数，则得到全部满足条件的素数： d = 1, 2, 4, 6, 10, 12, 30, 40, 60 对应： p = 2, 3, 5, 7, 11, 13, 31, 41, 61 取 a = 17（与上述所有 p 均互质，且为奇数）。 令 k = 120 / (p − 1)，若 k 为偶数则 17⁶⁰ ≡ +1 (mod p)，若 k 为奇数则 17⁶⁰ ≡ −1 (mod p)。 列表如下： 素数 p p − 1 k = 120/(p−1) 奇偶性 归属因子 2 — — — 17⁶⁰ ± 1 均为偶数，2 同时整除两者 3 2 60 偶数 17⁶⁰ − 1 5 4 30 偶数 17⁶⁰ − 1 7 6 20 偶数 17⁶⁰ − 1 11 10 12 偶数 17⁶⁰ − 1 13 12 10 偶数 17⁶⁰ − 1 31 30 4 偶数 17⁶⁰ − 1 41 40 3 奇数 17⁶⁰ + 1 61 60 2 偶数 17⁶⁰ − 1 结论 这 9 个素数（2, 3, 5, 7, 11, 13, 31, 41, 61）全部准确地”落入”了 17⁶⁰ − 1 或 17⁶⁰ + 1 的因子 中。没有遗漏任何一个，也没有因不互质而导致的无效情况。 定理核心意义 这个定理把寻找巨大数 aⁿ⁻¹ ± 1 的素因子这件事，彻底转化为了检查 2(n − 1) 的因子加 1 是 否为素数。该推广（将 p − 1 改为 (p − 1)/2，并用 ±1 兜底），使得结论对 n 的奇偶性完全免 疫，是一个极其漂亮且实用的数论工具。 |
回复此楼» 猜你喜欢
只有每年这种时候来逛逛小木虫
已经有23人回复
-
估计是周四
已经有3人回复
-
基金啊基金
已经有3人回复
-
科研孤儿太难了
已经有15人回复
-
让我中一个面上吧！
已经有10人回复
-
言之凿凿，明天官网会通知放榜？
已经有17人回复
-
时间戳又变了
已经有17人回复
-
今天系统多次维护，明天很可能放榜！
已经有11人回复
-
时间戳变了，能看出什么问题？
已经有23人回复
-
放榜前的不淡定
已经有12人回复
