Определение Множество натуральных чисел

Доказательство [I]. Пусть A = { c₁a₁ + c₂a₂ + ... + c_ka_k | с_i Z} — множество всевозможных целочисленных линейных комбинаций чисел а₁, а₂,.... а_k. Будем считать, что не вес числа а₁, а₂,… а_k нулевые, тогда в множестве А существует наименьший положительный элемент. Обо­значим его d. Покажем, что множество А совпадает с множеством всех целых чисел, кратных d. Поскольку число d может быть представлено в виде линейной комбинации чисел а₁, а₂, ....a_k то и любое число вида x_id где x Z, может быть представлено в виде линейной комбинации этих чисел.
Обратно, любая линейная комбинация чисел а₁, а₂ …а_k делится на d. Действительно, применим к числу d и произвольному элементу у А теорему о делении с остатком: существуют такие целые числа q и r, что y=qd+ r, причем 0≤r<d. Число r=y — qd является элементом множества А. поскольку у А и d А. Но d — наименьший неотрица­тельный элемент множества А, значит, r = 0 и y=qd. Таким образом, A={x d|x_i }.
Осталось доказать, что d — это наибольший общий делитель чисел a₁, а₂…a_k. Каждое из этих чисел имеет вид x_id, где х Z (достаточно рассмотреть линейную комбинацию вида 0*a1 + 0*a₂ + … + 0 * a_i-1 + 1*а_i, + 0 *a_i+1 +… + 0 * а_k). Таким образом, d — общий делитель чисел а₁, а₂,.... a_k.
Пусть с — любой другой делитель этих чисел. Тогда по свойству 2 делимости с делит каждую линейную комбинацию вида с₁а₁ + c₂a₂ + ... + c_ka_k, в том числе и ту, которая равна d. □
Определение 1.7. Целые числа а₁, a₂, .... а_к называются вза­имно простыми в совокупности, если НОД(а₁, а₂,.... а_k) = 1. Целые чис­ла а и b называются взаимно простыми, если НОД(а, b)=1.
Определение 1.8. Целые числа а₁ а₂, .... a_k называются по­парно взаимно простыми, если НОД(a_i, а_j)= 1 для всех 1 ≤ i≠j ≤ k.
Взаимно простые числа обладают следующими свойствами.

1. 
   Для того чтобы целые числа а₁, а₂, .... a_k были взаимно просты­ми в совокупности, необходимо и достаточно, чтобы существовали та­кие целые числа с₁, с₂,…с_k, что c₁a₁ + c₂a₂ + ... + с_kа_k⁼ 1
   

Доказательство. Необходимость следует из теоремы о существо­вании и линейном представлении наибольшего общего делителя. Дока­жем достаточность. Пусть целые числа с₁,c₂…с_k таковы, что c₁a₁ + c₂a₂ + ... + с_kа_k⁼1 и пусть d= НОД(a₁ ,a₂,…, a_k). Тогда, по опре­делению наибольшего общего делителя, каждое из чисел а₁, а₂, ..., а_к делится на d. Значит, по свойству 2 делимости, и сумма c₁a₁ + c₂a₂ + ... + с_kа_k делится на d, то есть 1 делится на d, следовательно, по свойству 6 делимости, d = 1. Таким образом, 1 = НОД(a₁, а₂,..., а_k) и числа a_i взаимно просты в совокупности.
1’. Для того чтобы целые числа а, b были взаимно простыми, необ­ходимо и достаточно, чтобы существовали такие целые числа m, п, что та + nb = 1.

2. 
   Пусть произведение ab делится на с и НОД(а, с) = 1. Тогда b де­лится на с.
   

Доказательство. Числа а и с взаимно просты, тогда, по свойству 1’, существуют такие целые числа т, n, что та + пс =1. Домножим обе части последнего равенства на b:
mab + ncb = b.
Первое слагаемое в левой части равенства делится на с по усло­вию. Второе слагаемое, очевидно, делится на с. Значит, и b делится на с.
□

3. Если НОД(а, b) = 1, НОД(а, с) = 1, то НОД(a, bс) = 1.

Доказательство. Числа а и b взаимно просты, поэтому по свойст­ву 1' число 1 можно представить в виде 1 = та + пb, где числа т и n це­лые. Умножим обе части этого равенства на с, получим
с = mac + nbc.
Пусть d — наибольший общий делитель чисел а и bc. Тогда оба слагаемых в правой части равенства делятся на d, а значит и число с де­лится на d. Но 1 — наибольший общий делитель чисел а и с, то есть 1 делится на d и d= 1. □

4. 
   ^{Если НОД(a,b1)=1, НОД(а,b2)=1, .... НОД(а,bk)=1, то}
   

НОД(а,b₁b₂..b_k)= 1.

5. 
   Пусть целые числа а₁, а₂, .... а_l, b₁, b₂, .... b_k таковы, что
   НОД(а_i,b_j)=1 для всех 1≤ i≤ l, 1≤ j≤ k. Тогда НОД(a₁a₂..a_l,b₁,b₂...b_k)=1.
   

5. 
   Пусть целое число а делится на b₁ и на b₂, НОД(b₁ b₂) = 1. Тогда a делится на произведение b₁b₂.
   

Доказательство. Число а делится на b₁ поэтому существует такое целое число с, что a = cb₁.
Так как а делится на b₂. то произведение cb₁ делится на b₂ Но по­скольку НОД(b₁ b₂) = 1, значит, по свойству 2 взаимно простых чисел, с делится на b₂, то есть существует такое целое число d. что с = db₂. Отсю­да а = cb₁ = db₁b₂, то есть а делится на b₁b₂, □

7. 
   Если а делится на каждое из попарно взаимно простых чисел b₁, b₂,...b_k, то а делится на произведение b₁b₂...b_k.
   

Определение 1.9. Целое число М называется наименьшим
общим кратным целых чисел а₁, а₂,…,а_k, аi≠0 для i=1, 2, .... k (обозначается М=НОК(a₁, а₂, .... a_k)), если выполняются следующие усло­вия:

1. 
   М делится на каждое из чисел а₁,а₂, ....a_k;
   
2. 
   если M_t — другое общее кратное чисел a_1, а₂,.... a_k, то M_t делится на М.
   

Наибольший общий делитель и наименьшее общее кратное двух положительных целых чисел связаны соотношением:

НОД(а, b) • НОК(а, b) = аb.

1.3. Вычисление наибольшего общего делителя

1.3.1. Алгоритм Евклида
Для вычисления наибольшего общего делителя двух целых чисел применяется способ повторного деления с остатком, называемый алго­ритмом Евклида.
Алгоритм 1.1. Алгоритм Евклида.
Вход. Целые числа а, b; 0 < b ≤ а.
Выход. d=НОД (a, b).

1. 
   ^{Положить r0 ← a, r1← b, i ← 1.}
   
2. 
   Найти остаток r_i+1 от деления r_i-1 на r_i.
   

3. 
   Если r_i+1=0, то положить d←r_i. В противном случае положить i ← i + 1 и вернуться на шаг 2.
   
4. 
   Результат: d.
   

Сложность алгоритма Евклида равна O(log²a)

Для доказательства корректности алгоритма Евклида нам понадо­бятся две леммы.
Лемма 1.5. Если числа а и b целые и а делится на b, то b=НОД(а, b).