整数唯一分解定理

整数唯一分解定理,也称为算术基本定理,是由德国数学家高斯在其著作《算术研究》中首次提出的。本文回顾整数唯一分解定理以及对应的几个重要结论。
在这里插入图片描述

一、整数唯一分解定理

整数唯一分解定理,也称为算术基本定理,是数论中的一个重要定理。它指的是每个大于1的整数都可以唯一地表示为几个素数的乘积,而且这些素数的幂都是正整数。
n = p 1 a 1 ∗ p 2 a 2 ∗ … ∗ p k a k (1) n = p_1^{a_1} * p_2^{a_2} * … * p_k^{a_k}\tag1 n=p1a1p2a2pkak(1)

整数唯一分解的C++代码如下:

void IntDecompose(int n) {map<int,int> maps;  		//存储质数以及对应的幂int i = 2, e = 0;while (n != 1) {if (n % i == 0) {n /= i;maps[i]++;}else i++;}auto it = maps.begin();		//输出n对应的分解结果cout << n << "=" << it->first << "^" << it->second;for (++it; it != maps.end(); ++it)cout << " * " << it->first << "^" << it->second;
}

二、数的约数个数

根据整数唯一分解定理,可以得到一个结论: n n n 的正约数的个数为:
F ( n ) = ( a 1 + 1 ) ∗ ( a 2 + 1 ) ∗ ⋯ ( a k + 1 ) (2) F(n) = (a_1+1)*(a_2+1)*\cdots (a_k+1)\tag2 F(n)=(a1+1)(a2+1)(ak+1)(2)
证明:对于 p i a i p_i^{a_i} piai, 它包含的因子有: p i 0 , p i 1 , p i 2 , ⋯ , p i a i p_i^0, p_i^1,p_i^2,\cdots ,p_i^{a_i} pi0,pi1,pi2,,piai a i + 1 a_i+1 ai+1个因子。同时,还可以进行组合,具体而言,可以
p 1 p_1 p1中取1个因子,有 a i + 1 a_i+1 ai+1种取法;
p 2 p_2 p2中取1个因子,有 a 2 + 1 a_2+1 a2+1种取法;
…;
p k p_k pk中取1个因子,有 a k + 1 a_k+1 ak+1种取法。
然后将他们连乘起来。
总的数目为: F ( n ) = ( a 1 + 1 ) ∗ ( a 2 + 1 ) ∗ ⋯ ( a k + 1 ) F(n) = (a_1+1)*(a_2+1)*\cdots (a_k+1) F(n)=(a1+1)(a2+1)(ak+1)

三、最大公约数和最小公倍数

给定两个数 x x x y y y,他们可以分解为相同素数的幂的乘积:
x = p 1 a 1 ∗ p 2 a 2 ∗ … ∗ p k a k x = p_1^{a_1} * p_2^{a_2} * … * p_k^{a_k} x=p1a1p2a2pkak y = p 1 b 1 ∗ p 2 b 2 ∗ … ∗ p k b k (3) y = p_1^{b_1} * p_2^{b_2} * … * p_k^{b_k} \tag3 y=p1b1p2b2pkbk(3)
例如:给定 x = 100 , y = 210 x = 100, y = 210 x=100,y=210 则:
100 = 2 2 ∗ 3 0 ∗ 5 2 ∗ 7 0 100 = 2^2 * 3^0 *5^2*7^0 100=22305270 210 = 2 1 ∗ 3 1 ∗ 5 1 ∗ 7 1 210=2^1 * 3^1 * 5^1 *7^1 210=21315171

3.1 最大公约数

给定式(3)所示的两个数 x , y x,y x,y, 它们的最大公约数为:
gcd ( x , y ) = p 1 m i n ( a 1 , b 1 ) ∗ p 2 m i n ( a 2 , b 2 ) ∗ … ∗ p k m i n ( a k , b k ) (4) \text{gcd}(x,y) = p_1^{min(a_1,b_1)} * p_2^{min(a_2,b_2)} * … * p_k^{min(a_k,b_k)} \tag4 gcd(x,y)=p1min(a1,b1)p2min(a2,b2)pkmin(ak,bk)(4)
简单证明:
首先, gcd ( x , y ) \text{gcd}(x,y) gcd(x,y) 一定能整除 x x x y y y。因为这里所有素数的幂都是取的较小者,即 p i p_i pi 的幂为 m i n ( a i , b i ) min(a_i,b_i) min(ai,bi), 所以 p i m i n ( a i , b i ) ∣ p i a i p_i^{min(a_i,b_i)} | p_i^{a_i} pimin(ai,bi)piai p i m i n ( a i , b i ) ∣ p i b i p_i^{min(a_i,b_i)} | p_i^{b_i} pimin(ai,bi)pibi。 因此 gcd ( x , y ) \text{gcd}(x,y) gcd(x,y) 一定能够整除 x x x y y y

那么,为什么 gcd ( x , y ) \text{gcd}(x,y) gcd(x,y) x x x y y y 的最大公约数呢?这里使用反证法。
假设 g g g 才是 x x x y y y 的最大公约数。
那么,必然存在 g g g 包含的某个素数 p i p_i pi 的指数 c i > m i n ( a i , b i ) c_i > min(a_i,b_i) ci>min(ai,bi)
但是,此时 p i c i p_i^{c_i} pici 要么不能整除 p i a i p_i^{a_i} piai, 要么不能整除 p i b i p_i^{b_i} pibi
因此, g g g 不能同时整除 x x x y y y
所以,与假设矛盾, gcd ( x , y ) \text{gcd}(x,y) gcd(x,y) 才是 x x x y y y 的最大公约数。

3.2 最小公倍数

给定式(3)所示的两个数 x , y x,y x,y, 它们的最小公倍数为:
lcm ( x , y ) = p 1 m a x ( a 1 , b 1 ) ∗ p 2 m a x ( a 2 , b 2 ) ∗ … ∗ p k m a x ( a k , b k ) (5) \text{lcm}(x,y) = p_1^{max(a_1,b_1)} * p_2^{max(a_2,b_2)} * … * p_k^{max(a_k,b_k)} \tag5 lcm(x,y)=p1max(a1,b1)p2max(a2,b2)pkmax(ak,bk)(5)
证明过程与最大公约数类似。

有了最大公约数和最小公倍数的定义,我们得出一个重要的结论:
x y = gcd ( x , y ) ∗ lcm ( x , y ) (4) xy = \text{gcd}(x,y)*\text{lcm}(x,y)\tag4 xy=gcd(x,y)lcm(x,y)(4)
因为 :
( p 1 m i n ( a 1 , b 1 ) ∗ p 2 m i n ( a 2 , b 2 ) ∗ … ∗ p k m i n ( a k , b k ) ) ∗ ( p 1 m a x ( a 1 , b 1 ) ∗ p 2 m a x ( a 2 , b 2 ) ∗ … ∗ p k m a x ( a k , b k ) ) = p 1 a 1 + b 1 ∗ p 2 a 2 + b 2 ∗ … ∗ p k a k + b k = x y \left(p_1^{min(a_1,b_1)} * p_2^{min(a_2,b_2)} * … * p_k^{min(a_k,b_k)}\right) *\left(p_1^{max(a_1,b_1)} * p_2^{max(a_2,b_2)} * … * p_k^{max(a_k,b_k)}\right) = p_1^{a_1+b_1} * p_2^{a_2+b_2} * … * p_k^{a_k+b_k}=xy (p1min(a1,b1)p2min(a2,b2)pkmin(ak,bk))(p1max(a1,b1)p2max(a2,b2)pkmax(ak,bk))=p1a1+b1p2a2+b2pkak+bk=xy

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/17968.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

对Pod做一个详细了解

文章目录 01创建一个pod02删除pod03镜像拉取策略04pod的标签05pod资源限制方法06pod的重启策略 07pod中运行多个容器08对pod内的容器执行命令09 验证多个pod中多个容器网络共享10 pod的创建流程和调度的约束方式pod的声明周期介绍pod 的健康检查健康检查的方式probe的探测方式案…

LinkedHashMap实现LRU

LRU 环境&#xff1a;JDK11 最近接触LRU(Least Recently Used)&#xff0c;即最近最少使用&#xff0c;也称淘汰算法&#xff0c;在JDK中LinkedHashMap有相关实现 LRU的LinkedHashMap实现 LinkedHashMap继承HashMap。所以内存的存储结构和HashMap一样&#xff0c;但是LinkedH…

基于rk356x u-boot版本功能分析及编译相关(三)Makefile分析

🎏技术驱动源于热爱,祝各位学有所成。 文章目录 一、Makefile简要概述二、简要流程图三、Makefile文件具体分析大家好哈,这次因工作比较忙,文章更新拖的有些久了。哈哈,话不多说,咱们接着上次继续说u-boot的Makefile。 一、Makefile简要概述 一般要了解u-boot源码的编译…

shell(1)脚本创建执行与变量使用

shell&#xff08;1&#xff09;脚本创建执行与变量使用 声明&#xff01; 学习视频来自B站up主 泷羽sec 有兴趣的师傅可以关注一下&#xff0c;如涉及侵权马上删除文章 笔记只是方便各位师傅的学习和探讨&#xff0c;文章所提到的网站以及内容&#xff0c;只做学习交流&…

第5章总体设计-5.4 硬件可行性分析

5.4 硬件可行性分析 5.4.1 硬件方案评估1. 框式产品硬件可行性分析&#xff08;1&#xff09;机框设计可行性。&#xff08;2&#xff09;单板设计可行性。&#xff08;3&#xff09;核心功能器件选型。&#xff08;4&#xff09;数据流。 2. 盒式产品硬件可行性分析3. 终端产品…

TOIS24|推荐公平性的反事实解释

论文&#xff1a;https://arxiv.org/pdf/2307.04386 代码&#xff1a;https://anonymous.4open.science/r/CFairER-anony/. 关键词&#xff1a;可解释推荐;公平;反事实的解释;强化学习 1 动机 现有推荐系统存在的公平性问题&#xff0c;例如性别歧视和种族偏见等&#xff0c;…

week 3 - Assembly Language

Important Instructions and Syntax 此内容是以MASM编写的&#xff0c;你将使用Visual C/C内联汇编来编程&#xff0c;因此数据元素的声明有所不同&#xff0c;但概念和指令集&#xff08;instruction sets)相同。 一、General-Purpose Registers 寄存器是CPU内的命名存储单元…

6.C操作符详解,深入探索操作符与字符串处理

C操作符详解&#xff0c;深入探索操作符与字符串处理 C语言往期系列文章目录 往期回顾&#xff1a; C语言是什么&#xff1f;编程界的‘常青树’&#xff0c;它的辉煌你不可不知VS 2022 社区版C语言的安装教程&#xff0c;不要再卡在下载0B/s啦C语言入门&#xff1a;解锁基础…

校园导航系统

关于数据结构的一个整理&#xff1a; 1、链式有序表的合并 2、栈 3、队列 4、二叉树、哈夫曼报文 5、图论 6、十大排序 7、校园导航系统 文章目录 校园导航系统演示示例代码示例1、弧结点和顶点节点2、Map节点3、用户 校园导航系统 采用C语言涉及了数据库相关的操作&am…

食品进出库库存管理发货开单软件下载 佳易王食品进出库管理系统操作教程

一、概述 【软件资源下载在文章最后】 食品进出库库存管理发货开单软件下载 食品进出库管理系统操作教程 商品进出库管理软件是一款操作简便的进出库管理软件&#xff0c;管理入库&#xff0c;出库&#xff0c;库存&#xff0c;同时打印发货单。 二、软件操作教程 第一步&a…

C++和OpenGL实现3D游戏编程【连载18】——加载OBJ三维模型

1、本节课要实现的内容 以前我们加载过立方体木箱,立方体的顶点数据都是在程序运行时临时定义的。但后期如果模型数量增多,模型逐步复杂,我们就必须加载外部模型文件。这节课我们就先了解一下加载OBJ模型文件的方法,这样可以让编程和设计进行分工合作,极大丰富我们游戏效…

二刷代码随想录第四天

24. 两两交换链表中的节点 设置个虚拟头节点画图理清楚节点之间的指向关系 class Solution { public:ListNode* swapPairs(ListNode* head) {ListNode* dummyHead new ListNode(0);dummyHead->next head;ListNode* cur dummyHead;while (cur->next ! nullptr &&…

【Linux】proc 文件系统详解

/proc 文件系统是 Linux 内核提供的一种特殊的文件系统&#xff0c;它主要用于显示内核和进程的信息。/proc 文件系统是一个虚拟文件系统&#xff0c;这意味着它并不占用实际的磁盘空间&#xff0c;而是由内核动态生成的内容。通过 /proc 文件系统&#xff0c;用户可以读取系统…

Linux文件系统

Linux文件系统 Linux 文件系统是 Linux 操作系统中用于存储和组织文件的结构。以下是一些关键概念和常见的 Linux 文件系统类型&#xff1a; 关键概念 文件系统层次结构&#xff1a;Linux 使用统一的文件系统层次结构&#xff0c;所有文件和目录都从根目录 / 开始。 目录结构…

[1.15.X-1.18.X]Herobrine-吾王HIM插件

Herobrine 这款插件99%自定义!为你的服务器增加一个吓人的HIM&#xff0c;该插件是一个非玩家角色&#xff0c;由 Minecraft 的粉丝创建。从来没有真正成为 Minecraft 游戏的一部分&#xff0c;这个故事是他在 Minecraft 世界里出没&#xff0c;Mojang 通过开玩笑地将“移除的 …

CTF 取证技术

01 流量分析 筛选器的使用 追踪流 文件导出 实例&#xff1a;通过筛选 http ,推断出 攻击者很可能 是 执行一个 文件上传 的攻击hack.php 很可能就是 攻击者 上传的 webshell依次进行 http 的 追踪流 查看查看到最后&#xff0c;发现响应中 有 PK文件头的存在 &#xff0c;说…

【GPIO】3.上/下 拉电阻通讯中的作用

一.什么是上/下拉电阻 上拉、下拉电阻统一称为拉电阻&#xff0c;作用是将状态不确定的信号线通过一个电阻将其箝位至高电平&#xff08;上拉&#xff09;或低电平&#xff08;下拉&#xff09; 这里有人可能会疑惑&#xff1f; 什么叫状态不确定的信号&#xff1f; 在数字电…

分享购:前期布局与后期问题解决策略

在当今电商与消费模式不断创新的时代&#xff0c;分享购作为一种极具潜力的商业模式&#xff0c;正受到越来越多的关注。然而&#xff0c;要想让分享购真正发挥优势、实现可持续发展&#xff0c;无论是前期的精心布局&#xff0c;还是后期妥善应对各类问题&#xff0c;都至关重…

51c大模型~合集46

我自己的原文哦~ https://blog.51cto.com/whaosoft/11908179 #HITS 北大李戈团队提出大模型单测生成新方法&#xff0c;显著提升代码测试覆盖率 单元测试是软件开发流程中的一个关键环节&#xff0c;主要用于验证软件中的最小可测试单元&#xff0c;函数或模块是否按预期工作…

中断与异常处理:走进代码

在操作系统的核心部分&#xff0c;中断&#xff08;Interrupt&#xff09;和异常&#xff08;Exception&#xff09;的处理机制是不可或缺的基础。它们的设计决定了系统的响应能力、稳定性和可扩展性。本文将深入探讨 Linux 内核中的中断与异常处理机制&#xff0c;并结合更多实…