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


初中数学竞赛讲座——数论部分5(最小公倍数)

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室 例 4 已知两正整数之和为 667,它们的最小公倍数除以最大公约数,商等于 120,求这两 个正整数。 解:...