logo search
Th_Numb+Combi (2)

Основные свойства наибольшего общего делителя и наименьшего общего кратного

Непосредственно из определений получаем следующие два свойства:

10. Для любых не равных одновременно нулю целых чисел a1 , … , an и произвольной перестановки (i1 , … , in) символов 1, … , n справедливо равенство НОД(a1 , … , an) = НОД().

20. Для любых чисел a, b Z, не равных одновременно нулю, справедливы равенства НОД(a, b) = НОД(–a, b) = НОД(a, –b).

Эти равенства легко следуют из общего принципа: если множества общих делителей чисел a1 , … , an совпадает с множеством общих делителей чисел b1 , … , bm , то совпадают и наибольшие элементы этих множеств: НОД(a1 , … , an) = НОД(b1 , … , bm).

30. Для любых ненулевых целых чисел a1 , … , an произвольной перестановки (i1 , … , in) символов 1, … , n справедливо равенство НОК[a1 , … , an] = НОК[].

40. Для любых чисел a, b Z \ {0} справедливы равенства НОК[a, b] = НОК[–a, b] = НОК[a, –b].

Аналогично предыдущему, всё следует из общего принципа: если множества общих кратных чисел a1 , … , an совпадает с множеством общих кратных чисел b1 , … , bm , то совпадают и наименьшие элементы этих множеств: НОК(a1 , … , an) = НОК(b1 , … , bm).

50. Если a, b Z и a | b, то НОД(a, b) = |a| .

Действительно, |a| | a, |a| | b и значит, |a| (a, b) |a| , т.е. (a, b) = |a| .

60. Если a, b Z и a | b, то НОК[a, b] = |b| .

Действительно, a | |b|, b | |b| и |b| [a, b] |b| , т.е. [a, b] = |b| .

70. Для любых чисел a, b Z, не равных одновременно нулю, и произвольного t Z справедливы равенства

НОД(a, b) = НОД(a, b – at) = НОД(a – bt, b).

В самом деле, если d = (a, b), то d | a, d | b и значит, по свойствам делимости нацело, d | (b – at), т.е. d (a, b – at) = D. Обратно, если D | a и D | (b – at), то D | b = (b – at) + at. Значит, D d = (a, b) D, т.е. d = D . Второе равенство проверяется аналогично.

80. Любой общий делитель d не равных одновременно нулю целых чисел а, b делит их наибольший общий делитель D = НОД(a, b).

Достаточно предполагать, что a b > 0 (?!). Рассуждая от противного, выберем наименьшее натуральное число а, для которого утверждение не верно. Ясно, что a > 1, т.к. при a = 1 общими делителями чисел a, b будут только ±1 | НОД(1, b) = 1.

Рассмотрим число a1 = a – b. По доказанным выше свойствам (a1 , b) = = (a, b) = D , d – общий делитель чисел a1 и b, причём 0 а1 < a. Поэтому, ввиду выбора a, верно d | (a1 , b) = D.

90. Любое общее кратное K ненулевых целых чисел а, b делится на их наименьшее общее кратное k = [a, b].

Будем рассуждать от противного. Если K не делится на k , то деля с остатком, получим K = kq + r, где 0 < r < k. Поскольку K и k – общие кратные чисел a и b, число r также является общим кратным чисел a и b (?!) вопреки минимальности наименьшего общего кратного k.

100. Для любых натуральных чисел a, b справедливо равенство

НОК[a, b] = .

Пусть D = (a, b), a = Da1 , b = Db1 , где a1 , b1 – натуральные числа. Докажем, что целое число K = =Da1b1 является наименьшим общим кратным чисел a, b. Действительно, во-первых, K = ab1 = ba1 является общим кратным чисел a, b. Во-вторых, если k – наименьшее общее кратное, то k = am = bn для некоторых целых чисел m, n , причём m b1 и n a1 (т.к. k K). Пусть b1 = mq + r – формула деления с остатком. Тогда из a1m = b1n имеем Da1r = Da1b1 – Da1mq = a(b1 – mq) = b(a1 – nq) делится на а и на b, т.е. является общим кратным чисел а, b. При этом Da1r < Da1m = k . Это возможно только при r = 0, значит, b1 = mq и a1 = nq, т.е. числа а и b делятся на Dq d. Поэтому, q = 1 и K = k – наименьшее общее кратное, что и требовалось доказать.

110. Для любых целых чисел a, b справедливо равенство

НОК[a, b] = .

Замечание. Обобщение НОК[a1 , … , аn] = доказанной формулы на случай любого числа сомножителей неверно. Придумайте контрпример и исправьте формулу.

120. Для любых не равных одновременно нулю целых чисел a1 , … , an–1 , an справедлива формула (a1 , … , an) = ((a1 , … , an–1), an).

Действительно, пусть Dn = (a1 , … , an), Dn–1 = (a1 , … , an–1). Тогда Dn делит все числа a1 , … , an–1 , а значит, Dn | Dn–1 . Кроме того Dn | an , так что Dn | (Dn–1 , an). Поскольку (Dn–1 , an) – общий делитель чисел a1 , … , an (?!), имеем (Dn–1 , an) | Dn и окончательно Dn = (Dn–1 , an), что и требовалось доказать.

130. Для любых не равных одновременно нулю целых чисел a1 , … , an–1 , an справедлива формула (a1 , … , an) = (((…((a1 , a2), a3), … ), an–1), an).

Упражнения: 1. Докажите, что

a1 , … , an Z \ {0} [a1 , … , an] = [[a1 , … , an–1], an],

и значит, [a1 , … , an] = [[[…[[a1 , a2], a3], … ], an–1], an].

2. Верно ли, что

a, b, c Z \ {0} (ac, bc) = (a, b)c [ac, bc] = [a, b]c ?

3. Верно ли, что a, b Z \ {0} (a2, b2) = (a, b)2 [a2, b2] = [a, b]2 ?

4. Верно ли, что a, b, c Z \ {0} [(a, b), c] = c (a, b, c) = (a, b) ?