nbhkdz.com冰点文库

数论最大公约数与最小公倍数

时间:


第二讲 最大公约数与最小公倍数
知识点 设 a1 , a2 , . . . , ak ∈ Z. 若 d|ai (1 ≤ i ≤ k), 则 d 就称为 a1 , a2 , . . . , ak 的公约数; 若 ai |d(1 ≤ i ≤ k), 则 d 就称为 a1 , a2 , . . . , ak 的公倍数. 我们把公约数中最大的称为最大公约数(一定是正的), 把正

的公倍数中最小的称为最小公倍数. 若 a1 , a2 , . . . , an 的标准分解式为
m m
i pα i , a2 = i pβ i , . . . , an =

m
i pδ i ,

a1 =
i=1

i=1

i=1

其中 pi 为素数, αi , βi , . . . , δi 为非负整数, i = 1, 2, . . . , m. 则
m m
i pt i ,

(a1 , a2 , . . . , an ) =
i=1

[a1 , a 2 , . . . , a n ] =
i=1

i pγ i ,

其中 ti = min{αi , βi , . . . , δi }, γi = max{αi , βi , . . . , δi }. 辗转相除法(欧几里得算法):设 a, b ∈ N+ , 且 a > b, 由带余除法可得 a = bq1 + r1 , b = r1 q2 + r2 , 0 < r1 < b 0 < r2 < r1 ··· rn?2 = rn?1 qn + rn , rn?1 = rn qn+1 + rn+1 , 0 < rn < rn?1 rn+1 = 0

由于每进行一次带余除法, 余数至少减少 1, 即 b > r1 > · · · > rn > rn+1 , 而 b 为有限数. 因此, 必 有一个最多不超过 b 的正整数 n 存在, 使得 rn+1 = 0. 从而, rn = (rn+1 , rn ) = (rn , rn?1 ) = · · · = (r2 , r1 ) = (r1 , b) = (a, b). 把 rn 逐步回代可得如下定理. 裴蜀定理:设 a, b ∈ Z, (a, b) = d, 则存在 u, v ∈ Z, 使得 ua + vb = d. 关于最大公约数及最小公倍数一些常用的性质. (1) (a, b)[a, b] = |ab|.
+

(2) 若 a|b, a|c, 则 a|(b, c). (4) 设 (a, b) = 1, 则 (ac, b) = (c, b).

(3) 若 a|c, b|c, 则 [a, b]|c.

(5) 若 m ∈ N , 则 (am, bm) = m(a, b), [am, bm] = m[a, b]. (6) (a, b) = (a, b ± a).

例题选讲 例1. 确定所有的三元正整数组 (a, b, c), 使得 a + b + c 是 a, b, c 的最小公倍数.

1

例2. 设 a > 1, m, n > 0, 证明: (am ? 1, an ? 1) = a(m,n) ? 1.

例3. 若 n, a1 , a2 , . . . , ak 是整数, n ≥ a1 > a2 > · · · > ak > 0, 且对于所有的 i 和 j , ai 和 aj 的最小公倍数不超过 n. 证明: 对于 1 ≤ i ≤ k, iai ≤ n.

2

例4. 对于正整数 a0 < a1 < a2 < · · · < an , 证明: 1 1 1 1 + + ··· + ≤ 1 ? n. [a0 , a1 ] [a1 , a2 ] [an?1 , an ] 2

例5. 对于正整数 m, n, 用 (m, n) 与 [m, n] 分别表示 m, n 的最大公约数与最小公倍 数. 设正整数 a1 < a2 < · · · < an (n ≥ 2). 证明
n

an =
k=1

(ak , ak+1 )

的充分必要条件为 1 = a1

n k=1

1 , [ak , ak+1 ]

ak+1 = a1 .

3

例6. 设 k 个整数 1 < a1 < a2 < · · · < ak ≤ n 中, 任意两个数 ai , aj 的最小公倍 数 [ai , aj ] > n. 证明:
k 1 i=1 ai

<3 2.

例7. 证明:存在一个有理数

c d,

其中 d < 100, 能使 k ·

c d

= k·

73 100

, 对于 k =

1, 2, . . . , 99 成立. 这里 [x] 表示实数的整数部分, 即不超过 x 的最大整数.

4

例8. 设 a1 , a2 , . . . , an 为正整数, 均不超过 2n, n = 4. 证明
1≤i<j ≤n

min [ai , aj ] ≤ 6

n +1 , 2

其中 [ai , aj ] 表示 ai 和 aj 的最小公倍数.

作业: 1. 数列 101, 104, 116, . . . 的通项是 an = 100 + n2 , 其中 n = 1, 2, 3, . . .. 对于每一个 n, 用 dn 表示 an 与 an+1 的最大公约数. 求 dn 的最大值, 其中 n 取一切正整数. 2. 数列 {un } 定义为 u1 = 1, u2 = 1, un = un?1 + 2un?2 , n = 3, 4, . . .. 证明对任意自 然数 n, p(p > 1) 有 un+p = un+1 up + 2un up?1 . 求出 un 与 un+3 的最大公约数. 3. Mn 为 1, 2, . . . , n 的最小公倍数(如 M1 = 1, M2 = 2, M3 = 6, M4 = 12, M5 = 60, M6 = 60). 对什么样的正整数 n, Mn?1 = Mn 成立. 证明你的结论.

5


数论

数论_数学_自然科学_专业资料 暂无评价|0人阅读|0次下载|举报文档 数论_数学_自然科学_专业资料。2002 题二 最大公约数与最小公倍数问题 (20分) [问题描述]...

数论综合

数论综合_六年级数学_数学_小学教育_教育专区。1 数论综合(一)知识要点一、短...[想想练练]已知两数的最大公约数是 21,最小公倍数是 126,求这两个数的...

数论第一章--整除

ak 的公因数中最大的一个叫做最大 公因数(或最大公约数) ,记作 (a1 , ...总能选出 4 个数是互素的. 最小公倍数定义 整数 a1 , a2 , , an 的...

初等数论

) 有了素数及整除的定义后, 首先要考虑的就是公约数、 最大公约数、 公倍数、 最小公倍数。乍一看,这似乎就是中学内容。不错,根据初等数论的低落脚点, 这...

数学竞赛中的数论问题

采用数论题目,是数学竞赛四大支柱之一,四大 1 支柱是:代数,几何,初等数论,组合...11 等数整除的判定;素数和合数,最大公约数与最小公倍数; 奇数和偶数,奇偶性...

小学奥数可以分为计算、计数、数论、几何、

小学奥数可以分为计算、计数、数论、几何、应用题、行程、组合七大板块,其中必须...(2)两个数最大公约数与最小公倍数的乘积等于这两个数的乘积。 求最小公倍...

六年级奥数. 数论.质数、合数、约数、倍数 (ABC级).学...

数论.质数、合数、约数、倍数 (ABC级).学生版_学科竞赛_小学教育_教育专区。...注意:两个最简分数的最大公约数不能是整数,最小公倍数可以是整数.例如: ? ...

数论计数

数论计数_学科竞赛_小学教育_教育专区。整除性问题:用 1、2、3、4(每个数恰好...甲数是 36,甲、乙两数最大公约数是 4,最小公倍数是 288,那么乙数是 ...

[第11讲] 初等数论(1)整除(中)

最大公约数与最小公倍数 最大公约数是数论中的一个重要概念.设 a 、 b 不全为零,同时整除 a 、 b 的整数称为它们的公约 数.因为 a 、 b 不全为零,...

数论知识点

数论知识点_学科竞赛_小学教育_教育专区。数论总结进制1.十进制: 我们常用的进制...? 三、最大公约数与最小公倍数的常用性质 1. 两个自然数分别除以它们的最...