当前位置: 首页 > news >正文

最大公约数和最小公倍数

我们知道,两个数的最大公约数可以用过辗转相除法获得,而两个数的最小公倍数可以通过最大公约数求出。即:

\[\operatorname {lcm}(a,b) = ab \div \gcd(a, b) \]

证明:设 \(a = k_1 d,\; b = k_2 d,\; d = \gcd(a,b)\),因为 \(\operatorname {lcm}(a,b) = k_1 \times k_2 \times d\)。所以 \(\operatorname {lcm}(a,b) = ab \div d\)

这是最常见的情况,只涉及两个数那如果涉及多个数该怎么办。

多个数的最大公约数

首先我们知道,每个数 \(x\) 都可以分解成一堆质数相乘的形式。而最大公约数,就是所有数都有的质数的乘积而已,即 \(d = \prod_{i = 1}^k p_i^{\min(a_i, b_i,c_i)}\)

所以,每多一个数,这个最大公约数的限制就会增多,设 \(d = \gcd(a,b,c), d_1 = \gcd(a,b)\),那么自然有 \(d | d_1\)\(d_1\) 的限制少于 \(d\)),即 \(d\) 所含的质数 \(d_1\) 里面一定也含有,因此可以得到:\(\gcd(a,b,c) = \gcd(\gcd(a,b),c)\)

而这就是我们最常用的求多个数最大约数的方式,即:\(a,b,c\) 的最大公约数等于 \(a,b\) 的最大公约数和 \(c\) 的最大公约数。\(\gcd(a,b,c) = \gcd(\gcd(a,b),c)\)

或者从另一方面想,因为

\[\begin{aligned} &\gcd(a,b,c) = \prod_{i = 1}^k p_i^{\min(a_i, b_i,c_i)} = \prod_{i = 1}^k p_i^{\min(\min (a_i, b_i),c_i)}\\ &\gcd(a, b) = \prod_{i = 1}^k p_i^{\min(a_i, b_i)}\end{aligned} \]

因此:\(\gcd(a,b,c) = \gcd(\gcd(a,b),c)\)。这样可能更容易理解。

多个数的最小公倍数

和最小公约数不同,最小公倍数不是每个数都共有的质数乘积。而是每个数具有质数最大次数的乘积,即:$$d = \prod_{i = 1}^k p_i^{\max(a_i, b_i,c_i)}$$可以看出最小公倍数和最大公约数是正好反着来的。

根据这个原理来说,因为:

\[\begin{aligned} &\operatorname {lcm}(a,b,c) = \prod_{i = 1}^k p_i^{\max(a_i, b_i,c_i)} = \prod_{i = 1}^k p_i^{\max(\max(a_i, b_i),c_i)} \\ &\operatorname {lcm}(a,b) = \prod_{i = 1}^k p_i^{\max(a_i, b_i)} \end{aligned} \]

所以 \(\operatorname {lcm}(a,b,c) = \operatorname {lcm}(\operatorname {lcm}(a,b), c)\)。而我们又知道 \(\operatorname {lcm}(a,b) = ab \div d\),所以可以 \(\gcd\) 来求出 \(\operatorname {lcm}\)。这就是多个数的最小公倍数的处理办法。

http://www.hskmm.com/?act=detail&tid=22335

相关文章:

  • OpenSpeedy最新版下载,夸克百度网盘加速提速|游戏加速工具|官网入口
  • Nginx核心配备详解:访问控制、用户认证与HTTPS部署
  • 5. 最长回文子串
  • 基于Python+Vue开发的婚恋交友管理系统源码+运行步骤
  • 2025 年搅拌机设备厂家 TOP 企业品牌推荐排行榜,盘点磁混凝系统 / 发酵罐 / 刮泥机 / 推进式 / 脱硫侧搅拌机公司推荐!
  • 福州市 2025 国庆集训 Day1 前三题题解
  • Python常用数据类型详解:字符串、列表、字典全解析
  • 强连通,Tarjan,缩点
  • OI 笑传 #13
  • Python方案--交互式VR教育应用开发
  • 纯Qt代码实现onvif协议设备端/onvif设备模拟器/onvif虚拟监控设备/桌面转onvif
  • *补*““逆元求组合数”(费马小定理
  • C# WPF中Binding的 Source属性和ElementName属性有什么区别
  • Typora to Obsidian 迁移助手 (Typora-to-Obsidian-Migration-Helper)
  • 64. 最小路径和
  • 题解:P1020 [NOIP 1999 提高组] 导弹拦截
  • 哈希表专题
  • Meta基础设施演进与AI技术革命
  • 完整教程:Spring AI整合聊天模型DeepSeek
  • 2025 年焚烧炉厂家 TOP 企业品牌推荐排行榜!权威甄选实力与口碑俱佳的江苏焚烧炉 / 无锡焚烧炉推荐这十家公司!
  • 2025 年防腐涂料厂家 TOP 企业品牌推荐排行榜,乙烯基、环氧煤沥青、环氧防腐涂料、防腐涂料地坪 、防腐涂料水池推荐这十家公司!
  • 2025双氧水厂家权威推荐榜:优质供应与专业定制实力之选
  • Win环境下包管理工具
  • MX Round 11 解题报告
  • 用 C# 打造企业资产管理系统雏形——从控制台到完整模块设计 - 详解
  • java开发之微信机器人的二次开发
  • 10.1刷题计划一
  • 笔记本电脑重装系统后找不到5G WIFI无线网或蓝牙模块消失的解决方案
  • 菜鸟坚持记录-开头篇
  • AI+传统工作流:Photoshop/Excel的智能插件开发指南 - 实践