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


数论初步-最大公约数与最小公倍数

数论初步-最大公约数与最小公倍数_幼儿读物_幼儿教育_教育专区。数论初步--最大公约数与最小公倍数 经典例题:1 把一块长 90 厘米,宽 42 厘米的长方形铁板...

论最小公倍数和最大公约数的方法

和最小公倍数的方法 在小学教材中求最大公约数和最小公倍数的方法 和最小公倍数班级:08 数三班 学号:30308346 姓名:钟世校 初等数论是研究整数最基本性质的...

数论 最大公约数与最小公倍数(知识点+例题)

数论 最大公约数与最小公倍数(知识点+例题)_三年级数学_数学_小学教育_教育专区。数论 最大公约数与最小公倍数(知识点+例题)尽心...

数论4—公约数和公倍数

数论4—公约数和公倍数 隐藏>> 第四讲 最大公因数和最小公倍数一、基本概念和知识 1.公因数和最大公因数 公 数和最大公因数 几个数公有的因数,叫做这几...

行测备考技巧:最大公约数和最小公倍数重要性质

我们把这些称作数论基础,它包括奇偶数、质合数、 最小公倍数、最大公约数等,今天华图教育资深专家带着大家回顾下我们 学过的最大公约数与最小公倍数的有关知识...

数论因数与倍数因数个数

? 2,3? 三、最大公约数与最小公倍数的常用性质 1. 两个自然数分别除以它们的最大公约数,所得的商互质。 如果 m 为 A 、B 的最大公约数, 且 A ? ...

数论(3)23约数,倍数,完全平方数 3

数论(3)23约数,倍数,完全平方数 3_五年级数学_数学_小学教育_教育专区。-学...7 4 8 8 0 3 三、求几个分数的最小公倍数和最大公约数 (1)求几个...

第三讲数论---约数与倍数

第三讲 最大公约数与最小公倍数一、基本概念: 1.公约数和最大公约数 几个数公有的约数,叫做这几个数的公约数;其中最大的一个叫做最大公约数。 例如:12 ...

第2讲最大公约数与最小公倍数

陕西师大附中高中数学竞赛辅导讲义—数论专题 最大公约数与最小公倍数 第二讲 最大公约数与最小公倍数基础知识与典型例题 一 基础知识与典型例题约数与倍数: 知...

公务员行测备考:最大or最小公倍数

痛苦的过程,我们把这些称作数论 基础,它包括奇偶数、质合数、最小公倍数、最大公约数等,今天中公老师带着大家回顾下 我们学过的最大公约数与最小公倍数的有关...