整数唯一分解定理

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

一、整数唯一分解定理

整数唯一分解定理,也称为算术基本定理,是数论中的一个重要定理。它指的是每个大于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.rhkb.cn/news/472934.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

小版本大不同 | Navicat 17 新增 TiDB 功能

近日&#xff0c;Navicat 17 迎来了小版本更新。此次版本新增了对 PingCap 公司的 TiDB 开源分布式关系型数据库的支持&#xff0c;进一步拓展了 Navicat 的兼容边界。即日起&#xff0c;Navicat 17 所有用户可免费升级至最新版本&#xff0c;通过 Navicat 工具实现 TiDB 数据库…

【珠海科技学院主办,暨南大学协办 | IEEE出版 | EI检索稳定 】2024年健康大数据与智能医疗国际会议(ICHIH 2024)

#IEEE出版|EI稳定检索#主讲嘉宾阵容强大&#xff01;多位外籍专家出席报告 2024健康大数据与智能医疗国际会议&#xff08;ICHIH 2024&#xff09;2024 International Conference on Health Big Data and Intelligent Healthcare 会议简介 2024健康大数据与智能医疗国际会议…

ADS项目笔记 1. 低噪声放大器LNA天线一体化设计

在传统射频结构的设计中&#xff0c;天线模块和有源电路部分相互分离&#xff0c;两者之间通过 50 Ω 传输线级联&#xff0c;这种设计需要在有源电路和天线之间建立无源网络&#xff0c;包括天线模块的输入匹配网络以及有源电路的匹配网络。这些无源网络不仅增加了系统的插入损…

客厅打苍蝇fly测试总结1116

项目介绍:本项目是关系食品安全重大项目&#xff0c;针对屋子里有苍蝇的问题&#xff0c;通过分析苍蝇特性及对场景分类&#xff0c;设计测试用例16条&#xff0c;有效击杀苍蝇17头&#xff0c;房间里面已经看不到苍蝇的活动痕迹。比较传统蚊拍击打容易在物体表面形成难看且赃的…

物理hack

声明 声明 文章只是方便各位师傅学习知识&#xff0c;以下网站只涉及学习内容&#xff0c;其他的都与本人无关&#xff0c;切莫逾越法律红线&#xff0c;否则后果自负。 ✍&#x1f3fb;作者简介&#xff1a;致力于网络安全领域&#xff0c;目前作为一名学习者&#xff0c;很荣…

go 集成swagger 在线接口文档

安装swaggo go install github.com/swaggo/swag/cmd/swaglatest 编写swag import ("github.com/gin-gonic/gin""goWeb/internal/service""goWeb/model/response" )// UserRouter 路由 func UserRouter(ctx *gin.RouterGroup) {ctx.GET("/…

学习threejs,使用第一视角控制器FirstPersonControls控制相机

&#x1f468;‍⚕️ 主页&#xff1a; gis分享者 &#x1f468;‍⚕️ 感谢各位大佬 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍⚕️ 收录于专栏&#xff1a;threejs gis工程师 文章目录 一、&#x1f340;前言1.1 ☘️第一视角控制器FirstPerson…

基于Java Web 的家乡特色菜推荐系统

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…

HMI FUXA测试

Foxa官网 foxa tutorialhttps://github.com/frangoteam/FUXA/wiki/Getting-Started 1 概述 FUXA是基于Web的&#xff0c;过程&#xff08;SCADA、HMI、看板等&#xff09;可视化软件。可创建现代的过程可视化&#xff0c;使用独立的设计器&#xff0c;显示机器和实时数据。 …

数据分析-Excel基础操作

目录 周报讲解 基础概念 理解数据 筛选excel表 数据透视表 插入数据透视表 新建字段 切片器&#xff08;筛选&#xff09; 数据透视图 Excel常用函数 sum&#xff08;求和&#xff09; 1-8月GMV 1月和8月GMV sumif&#xff08;条件求和&#xff09; sumifs 日G…

git创建远程仓库,以gitee码云为例GitHub同理

git远程Remote服务端仓库构建的视频教程在这 Git建立服务端Remote远程仓库&#xff0c;gitee码云例&#xff0c;Github_哔哩哔哩_bilibili 1、登gitee码云/Github 登录 - Gitee.com https://github.com/ &#xff08;没账号的注册一下就行&#xff09; 点击如下图位置的创…

【Android、IOS、Flutter、鸿蒙、ReactNative 】启动页

Android 设置启动页 自定义 splash.xml 通过themes.xml配置启动页背景图 IOS 设置启动页 LaunchScreen.storyboard 设置为启动页 storyboard页面绘制 Assets.xcassets 目录下导入图片 AppLogo Flutter 设置启动页 Flutter Android 设置启动页 自定义 launch_background.xm…

深入理解Flutter生命周期函数之StatefulWidget(一)

目录 前言 1.为什么需要生命周期函数 2.开发过程中常用的生命周期函数 1.initState() 2.didChangeDependencies() 3.build() 4.didUpdateWidget() 5.setState() 6.deactivate() 7.dispose() 3.Flutter生命周期总结 1.调用顺序 2.函数调用时机以及主要作用 4.生…

MacOS下,如何在Safari浏览器中打开或关闭页面中的图片文字翻译功能

MacOS下&#xff0c;如何在Safari浏览器中打开或关闭页面中的图片文字翻译功能 在Mac上的Safari浏览器中&#xff0c;可以通过实况文本功能来实现图片中的文本翻译。关闭步骤具体步骤如下&#xff1a; 在浏览器地址栏&#xff0c;鼠标右击翻译按钮&#xff0c;然后点击“首选…

IDC 报告:百度智能云 VectorDB 优势数量 TOP 1

近日&#xff0c;IDC 发布了《RAG 与向量数据库市场前景预测》报告&#xff0c;深入剖析了检索增强生成&#xff08;RAG&#xff09;技术和向量数据库市场的发展趋势。报告不仅绘制了 RAG 技术的发展蓝图&#xff0c;还评估了市场上的主要厂商。在这一评估中&#xff0c;百度智…

本地部署Apache Answer搭建高效的知识型社区并一键发布到公网流程

文章目录 前言1. 本地安装Docker2. 本地部署Apache Answer2.1 设置语言选择简体中文2.2 配置数据库2.3 创建配置文件2.4 填写基本信息 3. 如何使用Apache Answer3.1 后台管理3.2 提问与回答3.3 查看主页回答情况 4. 公网远程访问本地 Apache Answer4.1 内网穿透工具安装4.2 创建…

逆向攻防世界CTF系列37-crackme

逆向攻防世界CTF系列37-crackme 参考https://blog.csdn.net/xiao__1bai/article/details/120230397 nspack的壳&#xff0c;查了一下好像是北斗的一个壳 没找到什么脱壳软件&#xff0c;只能手动脱壳了 手动脱壳的最终要的是ESP定律 ESP定律的原理就是“堆栈平衡”原理 涉及…

Chrome 浏览器开启打印模式

打开开发者工具ctrl shift p输入print 找到 Emulate CSS print media type

微服务链路追踪skywalking安装

‌SkyWalking是一个开源的分布式追踪系统&#xff0c;主要用于监控和分析微服务架构下的应用性能。‌ 它提供了分布式追踪、服务网格遥测分析、度量聚合和可视化一体化解决方案&#xff0c;特别适用于微服务、云原生架构和基于容器的环境&#xff08;如Docker、K8s、Mesos&…

数据结构-哈夫曼树

一.什么是哈夫曼树 不同搜索树的效率是不一样的,根据不同的频率构造效率比较好或者最好的搜索树就是哈夫曼树 二.哈夫曼树的定义 将带权路径的长度降低最低 每个叶子节点到根节点的距离乘权值&#xff0c;再全都加起来就得到了WPL值 第一颗二叉树:从上到下计算 5x14x23x32x41…