(12)梅森素数与完全数

news/2024/4/15 3:18:41

梅森素数与完全数

欧几里得完全数公式

如果 2 p − 1 2^p-1 2p1是素数,则 2 p − 1 ( 2 p − 1 ) 2^{p-1}(2^p-1) 2p1(2p1)是完全数。
验证 q = 2 p − 1 q=2^p-1 q=2p1,我们需要验证 2 p − 1 q 2^{p-1}q 2p1q是完全数。 2 p − 1 q 2^{p-1}q 2p1q的真因数是

1 , 2 , 4 , ⋯ , 2 p − 1 1,2,4,\cdots,2^{p-1} 1,2,4,,2p1 q , 2 q , 4 q , ⋯ , 2 p − 2 q q,2q,4q,\cdots,2^{p-2}q q,2q,4q,,2p2q

使用前一章的几何级数公式将这些数相加。几何级数公式说明

1 + x + x 2 + ⋯ + x n − 1 = x n − 1 x − 1 1+x+x^2+\cdots+x^{n-1}=\frac{x^n-1}{x-1} 1+x+x2++xn1=x1xn1

令x=2,n=p得

1 + 2 + 4 + ⋯ + 2 p − 1 = 2 p − 1 2 − 1 = 2 p − 1 = q 1+2+4+\cdots+2^{p-1}=\frac{2^p-1}{2-1}=2^p-1=q 1+2+4++2p1=212p1=2p1=q

可用x=2,n=p-1的公式计算

q + 2 q + 2 2 q + ⋯ + 2 p − 2 q = q ( 1 + 2 + 2 2 + ⋯ + 2 p − 2 = q ( 2 p − 1 − 1 2 − 1 ) = q ( 2 p − 1 − 1 ) q+2q+2^2q+\cdots+2^{p-2}q=q(1+2+2^2+\cdots+2^{p-2}=q(\frac{2^{p-1}-1}{2-1})=q(2^{p-1}-1) q+2q+22q++2p2q=q(1+2+22++2p2=q(212p11)=q(2p11)

如果将 2 p − 1 q 2^{p-1}q 2p1q的所有真因数相加,可得

q + q ( 2 p − 1 − 1 ) = 2 p − 1 q q+q(2^{p-1}-1)=2^{p-1}q q+q(2p11)=2p1q

这就证明了 2 p − 1 q 2^{p-1}q 2p1q是完全数。
事实上,求得一个梅森素数就得到了一个完全数。

欧拉完全数定理

如果n是偶完全数,则n形如

n = 2 p − 1 ( 2 p − 1 ) n=2^{p-1}(2^p-1) n=2p1(2p1)

其中 2 p − 1 2^p-1 2p1是梅森素数。
我们将在本章末尾证明欧拉定理,但首先需要讨论证明所需的函数。这个函数用希腊字母 σ \sigma σ表示,即

σ ( n ) = n 的 所 有 因 数 之 和 ( 包 括 1 与 n ) \sigma(n)=n的所有因数之和(包括1与n) σ(n)=n1n

σ \sigma σ函数公式

(a)如果p是素数, k ≥ 1 k\ge1 k1,则

σ ( p k ) = 1 + p + p 2 + ⋯ + p k = p k + 1 − 1 p − 1 \sigma(p^k)=1+p+p^2+\cdots+p^k=\frac{p^{k+1}-1}{p-1} σ(pk)=1+p+p2++pk=p1pk+11

(b)如果 g c d ( m , n ) = 1 gcd(m,n)=1 gcd(m,n)=1,则

σ ( m n ) = σ ( m ) σ ( n ) \sigma(mn)=\sigma(m)\sigma(n) σ(mn)=σ(m)σ(n)

正如 ϕ \phi ϕ函数一样,我们可使用 σ \sigma σ函数公式容易地计算大数值n的 σ ( n ) \sigma(n) σ(n)值。
证明(b)
注意,以下证明是个人通过个人所学写的,没有找到官方证明,仅供参考,欢迎指出错误。
通过算数基本定理我们可以将m写成

m = p 1 i 1 p 2 i 2 ⋯ p r i r m=p_1^{i_1}p_2^{i_2}\cdots p_r^{i_r} m=p1i1p2i2prir

其中p都是素数。而m的因数都可以写成

p 1 b 1 p 2 b 2 ⋯ p r b r p_1^{b_1}p_2^{b_2}\cdots p_r^{b_r} p1b1p2b2prbr

其中 b k ≤ i k ( 1 ≤ k ≤ r ) b_k\le i_k(1\le k\le r) bkik(1kr)
同理

n = q 1 j 1 q 2 j 2 ⋯ q s j s n=q_1^{j_1}q_2^{j_2}\cdots q_s^{j_s} n=q1j1q2j2qsjs

m的因数

q 1 c 1 q 2 c 2 ⋯ q s c s q_1^{c_1}q_2^{c_2}\cdots q_s^{c_s} q1c1q2c2qscs

其中 c k ≤ j k ( 1 ≤ k ≤ s ) c_k\le j_k(1\le k\le s) ckjk(1ks)
同理


m n = p 1 i 1 p 2 i 2 ⋯ p r i r q 1 j 1 q 2 j 2 ⋯ q s j s mn=p_1^{i_1}p_2^{i_2}\cdots p_r^{i_r}q_1^{j_1}q_2^{j_2}\cdots q_s^{j_s} mn=p1i1p2i2prirq1j1q2j2qsjs

mn的因数

p 1 b 1 p 2 b 2 ⋯ p r b r q 1 c 1 q 2 c 2 ⋯ q s c s p_1^{b_1}p_2^{b_2}\cdots p_r^{b_r}q_1^{c_1}q_2^{c_2}\cdots q_s^{c_s} p1b1p2b2prbrq1c1q2c2qscs

其中 b k ≤ i k ( 1 ≤ k ≤ r ) , c k ≤ j k ( 1 ≤ k ≤ s ) b_k\le i_k(1\le k\le r),c_k\le j_k(1\le k\le s) bkik(1kr)ckjk(1ks)

m的因数集为M,n的因数集为N,mn的因数集为MN那么我们要证明(b),只需要证明

M N = { i ∗ j ∣ i ∈ N , j ∈ M } MN=\{i*j|i\in N,j\in M\} MN={ijiN,jM}

因为

σ ( m n ) = σ ( m ) σ ( n ) \sigma(mn)=\sigma(m)\sigma(n) σ(mn)=σ(m)σ(n)
∑ M N = ∑ M ∗ ∑ N \sum{MN}=\sum{M}*\sum{N} MN=MN
∑ M N = ∑ { i ∗ j ∣ i ∈ N , j ∈ M } \sum{MN}=\sum\{i*j|i\in N,j\in M\} MN={ijiN,jM}

我们要证明二者相等我们需要证明两条
(1)涵盖
只需要注意到对于任意的 p 1 b 1 p 2 b 2 ⋯ p r b r p_1^{b_1}p_2^{b_2}\cdots p_r^{b_r} p1b1p2b2prbr,对应于乘积式里每个素数对应次幂的项的乘积。前者每一个数都会在后者集合中出现。
(2)不重复
我们假设a,b是后者集合中的不同的项,且a=b, a = p 1 b 1 p 2 b 2 ⋯ p r b r a=p_1^{b_1}p_2^{b_2}\cdots p_r^{b_r} a=p1b1p2b2prbr b = p 1 d 1 p 2 d 2 ⋯ p r d r b=p_1^{d_1}p_2^{d_2}\cdots p_r^{d_r} b=p1d1p2d2prdr,因为算数基本定理,一个数只有一种素因数分解,这与前面两种分解冲突了,所以后者没有重复项。

综上,得证。

欧拉完全数定理

如果n是偶完全数,则n形如

n = 2 p − 1 ( 2 p − 1 ) n=2^{p-1}(2^p-1) n=2p1(2p1)

其中 2 p − 1 2^p-1 2p1是梅森素数。
证明假设n是偶完全数。n是偶数说明可将它分解成

n = 2 k m , k ≥ 1 且 m 是 奇 数 n=2^km,k\ge1且m是奇数 n=2km,k1m

下面用 σ \sigma σ函数公式计算 σ ( n ) \sigma(n) σ(n)
σ ( n ) = σ ( 2 k m ) \sigma(n)=\sigma(2^km) σ(n)=σ(2km)因为 n = 2 k m , n=2^k m, n=2km,
= σ ( 2 k ) σ ( m ) =\sigma(2^k)\sigma(m) =σ(2k)σ(m)使用 σ \sigma σ的乘法公式与事实 g c d ( 2 k , m ) = 1 , gcd(2^k,m)=1, gcd(2k,m)=1,
= ( 2 k + 1 − 1 ) σ ( m ) =(2^{k+1}-1)\sigma(m) =(2k+11)σ(m)使用 p = 2 p=2 p=2 σ ( p k ) \sigma(p^k) σ(pk)的公式。

但由假设n是完全数,这意味着 σ ( n ) = 2 n = 2 k + 1 m \sigma(n)=2n=2^{k+1}m σ(n)=2n=2k+1m。所以得到 σ ( n ) \sigma(n) σ(n)的两种不同表示,且他们必然相等:

2 k + 1 m = ( 2 k + 1 − 1 ) σ ( m ) 2^{k+1}m=(2^{k+1}-1)\sigma(m) 2k+1m=(2k+11)σ(m)

显然 2 k + 1 − 1 2^{k+1}-1 2k+11是奇数,且 ( 2 k + 1 − 1 ) σ ( m ) (2^{k+1}-1)\sigma(m) (2k+11)σ(m) 2 k + 1 2^{k+1} 2k+1的倍数,所以 2 k + 1 2^{k+1} 2k+1必整除 σ ( m ) \sigma(m) σ(m)。换句话说,存在整数c使得 σ ( m ) = 2 k + 1 c \sigma(m)=2^{k+1}c σ(m)=2k+1c。将其代入前面的等式得

2 k + 1 m = ( 2 k + 1 − 1 ) σ ( m ) = ( 2 k + 1 − 1 ) 2 k + 1 c 2^{k+1}m=(2^{k+1}-1)\sigma(m)=(2^{k+1}-1)2^{k+1}c 2k+1m=(2k+11)σ(m)=(2k+11)2k+1c

从两边消去 2 k + 1 2^{k+1} 2k+1 m = ( 2 k + 1 − 1 ) c m=(2^{k+1}-1)c m=(2k+11)c
接下来我们通过假设 c > 1 c>1 c>1并推出错误结论来证明c=1,则 m = ( 2 k + 1 − 1 ) c m=(2^{k+1}-1)c m=(2k+11)c被不同的数1,c,m整除,不论何种情况,可求得

σ ( m ) ≥ 1 + c + m = 1 + c + ( 2 k + 1 − 1 ) c = 1 + 2 k + 1 c \sigma(m)\ge1+c+m=1+c+(2^{k+1}-1)c=1+2^{k+1}c σ(m)1+c+m=1+c+(2k+11)c=1+2k+1c

然而,我们还知道 σ ( m ) = 2 k + 1 c \sigma(m)=2^{k+1}c σ(m)=2k+1c所以

2 k + 1 c ≥ 1 + 2 k + 1 c 2^{k+1}c\ge1+2^{k+1}c 2k+1c1+2k+1c

这显然是荒谬的。这个矛盾表明c必等于1,即

m = ( 2 k + 1 − 1 ) 且 σ ( m ) = 2 k + 1 = m + 1 m=(2^{k+1}-1)且\sigma(m)=2^{k+1}=m+1 m=(2k+11)σ(m)=2k+1=m+1

显然m的因数只有1和m,所以m是素数。
现在我们证明了如果n是偶完全数,则

n = 2 k ( 2 k + 1 − 1 ) , 2 k + 1 − 1 是 素 数 n=2^k(2^{k+1}-1),2^{k+1}-1是素数 n=2k(2k+11),2k+11

如果 2 k + 1 − 1 2^{k+1}-1 2k+11是素数,则k+1本身必是素数,即 k + 1 = p k+1=p k+1=p。所以每个偶完全数形如 n = 2 p − 1 ( 2 p − 1 ) n=2^{p-1}(2^p-1) n=2p1(2p1)。其中 2 p − 1 2^p-1 2p1是梅森素数。这就完成了欧拉完全数定理的证明。

注意欧拉完全数定理给出了所有偶完全数的漂亮描述,但没有涉及有关奇完全数的任何东西。
奇完全数难题奇完全数是否存在没有人给出过证明。


http://www.ppmy.cn/news/731371.html

相关文章

<2>

前端开发: 前端开发也叫做web前端开发,它指的是基于web的互联网产品的页面(也叫界面)开发及功能开发 CtrlA:全选 HTML(是超文本标记语言) 超文本: 是一种组织信息的方法&#x…

缓存淘汰策略:LRU、LFU、FIFO 算法原理

通常来说,Redis 一共有 6 种缓存淘汰策略,其中,常用的 allkeys-lru 和 volatile-lru 里面都提到了 LRU 的概念,实际上 LRU 就是缓存淘汰策略的基础算法。现在,就由 LRU 引出今天要说的话题:学习 LRU、LFU、…

缓存淘汰算法(LRU)

1. LRU 原理 LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。 1.2. 实现 最常见的实现是使用一个链表保存缓…

高效复用ReentrantLock,基于2Q策略的细粒度Java锁池

为了实现更细粒度且有效率的控制锁,自定义了一个支持细颗粒度和高效复用的锁管理工具。 细颗粒度是通过维护锁池的key-value结构实现的,通过控制key来获得限制不同资源的锁。高效复用这一点是通过让锁池实现2Q缓存淘汰机制实现的。 具体实现是&#xf…

【跨平台网络抓包神器のtcpdump】ubuntu下编译tcpdump开源抓包工具

1.源码准备: (1)下载tcpdump源码:https://www.tcpdump.org/index.html#latest-releases (2)下载两个文件(tcpdump与libpcap):tcpdump-4.99.1.tar.gz和libpcap-1.10.1.tar.gz 2.linux编译环境准备 在linux编译机中,新…

图论典型问题--握手定理

离散数学期末考试要考握手定理&#xff0c;复习一下。 定理1 无向图 G < V , E > G<V,E> G<V,E> 是 ( p , q ) (p,q) (p,q)图( ∣ V ∣ p , ∣ E ∣ q |V|p,|E|q ∣V∣p,∣E∣q)&#xff0c;则 ∑ v ∈ V d G ( v ) 2 q \sum_{v\in{V}}d_{G}(v)2q ∑v∈V…

电磁场与波课设-关于多点电荷的电力线与等位面的matlab计算仿真

电磁场与波课设-关于多点电荷的电力线与等位面的matlab计算仿真 本文章记录了电磁场与波的课程设计-关于多点电荷的电力线与等位面的matlab计算仿真 三极子的仿真 直接进入正题三个电荷分布在正电荷&#xff08;-1&#xff0c;0&#xff09;、正电荷&#xff08;1&#xff0…

qml-小例子

1 电池电量显示 qmldemo电池电量显示-网管软件文档类资源-CSDN下载 2 Q_PROPERTY自定义数据使用 Qt属性系统及Q_PROPERTY宏的使用_龚建波的博客-CSDN博客 qmlq_propertylist使用-Typescript文档类资源-CSDN下载

*2·····

/* * Copyright (c) 2013, 烟台大学计算机学院 * All rights reserved. * 作 者&#xff1a; * 完成日期&#xff1a;2013 年 10月 * 版 本 号&#xff1a;v1.0 * 问题描述&#xff1a;输出*图 * 输入&#xff1a;* * 输出&#xff1a;图案 */ #include <iost…

MATLAB 数学应用 微分方程 边界值问题 求解具有未知参数的BVP

本文说明如何使用 bvp4c 求解具有未知参数的边界值问题。 马蒂厄方程在区间 [0,π] 上定义为 y ′ ′ ( λ − 2 q c o s ( 2 x ) ) y 0 y^{} (λ−2q cos(2x))y 0 y′′(λ−2q cos(2x))y0。 当参数 q5 时&#xff0c;边界条件为 y′(0)0&#xff0c; y′(π)0。 但这…

【通信系统仿真系列】基于延迟相乘鉴相的4Q-DPSK差分通信系统仿真

【通信系统仿真系列】基于延迟相乘鉴相的4Q-DPSK差分通信系统仿真 前言原理码元载波差分处理一次差分二次差分 调制加入噪声延迟相乘解调判决 实验结果仿真代码可修改的参数下载链接主函数仿真代码原理展示代码 调用函数码元生成模块载波生成模块差分模块调制模块解调模块判决模…

BetaFlight深入传感设计之六:四元数计算方法

BetaFlight深入传感设计之六&#xff1a;四元数计算方法 1. 四元数理论1.1 定义1.2 基本运算1.2.1 矢量加减1.2.2 标量乘法 1.3 矢量点叉乘1.3.1 矢量点乘1.3.2 矢量叉乘 1.4 除法求逆 2. 程序四元素2.1 四元数定义2.2 四元数初始化2.2.1 单位标量初始化2.2.2 矢量初始化 2.3 表…

缓存替换算法笔记 ——2Q

参考资料 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm 算法描述 2Q: two queue(s) algorithm 应用最广泛的缓存替换算法应该是LRU了&#xff0c;其实现简单有效。但正是因为其简单&#xff0c;对于某些访问场景来说表现并不出色。LRU用新访问…

关于佩尔方程的前X(多组)解,特例:p^2-2q^2=1

对于佩尔方程的简单求解&#xff08;特例&#xff09; 新手感悟&#xff1a; 在很多组解之后&#xff0c;佩尔方程的解组会变得非常大&#xff0c;则需要利用数组&#xff0c;将一个非常大的数变成单个的数字&#xff0c;并存放在数组中 基本思路&#xff1a; 1.数组乘法&…

缓存淘汰算法LRU-K,2Q(Two queues)

1.LRU-K 1.1 简介 LRU-K中的K代表最近使用的次数&#xff0c;LRU可以当作LRU-1。LRU-K主要目的是为了解决LRU算法的缓存污染问题。 什么是缓存污染&#xff1f; 当数据访问次数非常少&#xff0c;甚至只会被访问一次&#xff0c;数据服务完访问请求后还继续留在缓存中&…

Dragonfly单机部署比redis快25倍的缓存中间件

目录 ​编辑 简介 安装 底层原理 LRU LRU 执行效率 Redis 中的 LRU Dragonfly缓存 简介 Dragonfly 是一款高性能的缓存中间件&#xff0c;与 Redis 和 Memcached API 完全兼容&#xff0c;无缝对接&#xff08;意思就是开发人员直接改一下配置文件的链接地址即可&…

BCH码(能纠正多个随机错误的循环码)

PS&#xff1a;课上讲的也是编解码流程&#xff0c;也没有原理&#xff0c;网上也没找到每一步的原理&#xff0c;想要了解设计思路还是需要去找一下原版的论文。 参考blog&#xff1a; 【1】【举例子详细分析】BCH码(BCH code) 目录 1. 伽罗华域和多项式2. 提出背景和思路3. …

【通信系统仿真设计】基于Matlab的2Q-FSK移频键控通信系统仿真

基于Matlab的2Q-FSK移频键控通信系统仿真 前言仿真原理实验原理载波调制接收端接收加噪实现 解调滤波器滤波实现滤波结果图码元判决 实验结果实验结果拟合 仿真代码完整代码下载主函数双极性码生成模块载波生成模块调制模块滤波器生成器功率计算模块数组居中截取模块码元判决模…

LRU-K,2Q,LIRS算法介绍与比较

研究H2的过程中发现新的存储引擎MVStore使用了新的cache替换算法——LIRS,经过一系列相关的论文研读,发现比旧存储引擎PageStore的LRU算法改良不少。为了更好地了解LIRS的优异性,把同样属于LRU变种的基于倒数第二次访问时间对比进行cache替换的LRU-K(K一般为2)[1],2Q[2],…

常用缓存淘汰算法LFU、LRU、2Q、ARC

常用缓存淘汰算法LFU、LRU、2Q、ARC LRULFU2QARC LRU LRU(Least Recently Used) 是一种使用广泛的缓存数据替换策略&#xff0c;目的是在有限的内存空间中尽可能保留最有价值的缓存数据。 其核心本意是&#xff0c;在资源出现不足时&#xff0c;剔除掉最近最少使用的数据&…
最新文章