§ 3. Наибольший общий делитель и наименьшее общее кратное

Пусть a₁ , … , a_n – целые числа, одновременно не равные нулю. Их общим делителем называется любое целое число d, делящее все указанные числа. Ясно, что модуль |d| любого общего делителя d сам является общим делителем тех же чисел и 1  |d| min{ |a_i|  Z | a_i  0} (ввиду |a_i| = |d|q_i). Поэтому среди всех положительных общих делителей заданных целых чисел a₁ , … , a_n , существует однозначно определённый наибольший, который называется наибольшим общим делителем этих чисел и обозначается символом НОД(a₁ , … , a_n) или кратко – через (a₁ , … , a_n). Таким образом, число D = НОД(a₁ , … , a_n) полностью характеризуется следующими двумя условиями:

(D1): D | a₁  …  D | a_n (D – общий делитель чисел a₁ , … , a_n),

(D2):  d  Z d | a₁  …  d | a_n  |d|  D (D – наибольший среди положительных общих делителей чисел a₁ , … , a_n).

Примеры: (0, 2) = 2, (4, 6) = 2, (3, 5) = 1, (9, 6, 15) = 3, (0, 0) не определён.

Общим кратным ненулевых целых чисел a₁ , … , a_n называется любое целое число, делящееся одновременно на каждое из указанных чисел. Примерами общих кратных могут служить произведение a₁… a_n и его модуль |a₁…a_n|. Поэтому в конечном множестве {x  Z | |x|  |a₁…a_n| }, а значит, среди всех общих кратных заданных целых чисел a₁ , … , a_n существует однозначно определённое наименьшее положительное кратное, называемое их наименьшим общим кратным и обозначаемое символом НОК[a₁ , … , a_n] или просто через [a₁ ,… , a_n]. При этом очевидно, что

max{|a_i| | 1  i  n}  [a₁ ,… , a_n]  |a₁…a_n| .

Таким образом, натуральное число k = НОК[a₁ , … , a_n] полностью определяется следующими двумя условиями:

(К1): k  a₁  …  k  a_n (k – общее кратное чисел a₁ , … , a_n),

(К2):  K  N K  a₁  …  K  a_n  K  k (k – наименьшее среди всех положительных кратных).

Примеры: [0, 2] не определено, [4, 6] = 12, [3, 5] = 15, [9, 6, 15] = 90.