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


Download 1.44 Mb.
bet2/9
Sana02.06.2024
Hajmi1.44 Mb.
#1837140
TuriЗакон
1   2   3   4   5   6   7   8   9
Bog'liq
Символ Лежандра

Доказательство [I]. Пусть A = { c1a1 + c2a2 + ... + ckak | сi Z} — множество всевозможных целочисленных линейных комбинаций чисел а1, а2,.... аk. Будем считать, что не вес числа а1, а2, аk нулевые, тогда в множестве А существует наименьший положительный элемент. Обо­значим его d. Покажем, что множество А совпадает с множеством всех целых чисел, кратных d. Поскольку число d может быть представлено в виде линейной комбинации чисел а1, а2, ....ak то и любое число вида xid где x Z, может быть представлено в виде линейной комбинации этих чисел.
Обратно, любая линейная комбинация чисел а1, а2аk делится на d. Действительно, применим к числу d и произвольному элементу у А теорему о делении с остатком: существуют такие целые числа q и r, что y=qd+ r, причем 0r<d. Число r=yqd является элементом множества А. поскольку у А и d А. Но d — наименьший неотрица­тельный элемент множества А, значит, r = 0 и y=qd. Таким образом, A={x d|xi }.
Осталось доказать, что d — это наибольший общий делитель чисел a1, а2ak. Каждое из этих чисел имеет вид xid, где х Z (достаточно рассмотреть линейную комбинацию вида 0*a1 + 0*a2 + … + 0 * ai-1 + 1*аi, + 0 *ai+1 +… + 0 * аk). Таким образом, d — общий делитель чисел а1, а2,.... ak.
Пусть с — любой другой делитель этих чисел. Тогда по свойству 2 делимости с делит каждую линейную комбинацию вида с1а1 + c2a2 + ... + ckak, в том числе и ту, которая равна d. □
Определение 1.7. Целые числа а1, a2, .... ак называются вза­имно простыми в совокупности, если НОД(а1, а2,.... аk) = 1. Целые чис­ла а и b называются взаимно простыми, если НОД(а, b)=1.
Определение 1.8. Целые числа а1 а2, .... ak называются по­парно взаимно простыми, если НОД(ai, аj)= 1 для всех 1 ≤ ij k.
Взаимно простые числа обладают следующими свойствами.

  1. Для того чтобы целые числа а1, а2, .... ak были взаимно просты­ми в совокупности, необходимо и достаточно, чтобы существовали та­кие целые числа с1, с2,…сk, что c1a1 + c2a2 + ... + сkаk= 1

Доказательство. Необходимость следует из теоремы о существо­вании и линейном представлении наибольшего общего делителя. Дока­жем достаточность. Пусть целые числа с1,c2сk таковы, что c1a1 + c2a2 + ... + сkаk=1 и пусть d= НОД(a1 ,a2,…, ak). Тогда, по опре­делению наибольшего общего делителя, каждое из чисел а1, а2, ..., ак делится на d. Значит, по свойству 2 делимости, и сумма c1a1 + c2a2 + ... + сkаk делится на d, то есть 1 делится на d, следовательно, по свойству 6 делимости, d = 1. Таким образом, 1 = НОД(a1, а2,..., аk) и числа ai взаимно просты в совокупности.
1’. Для того чтобы целые числа а, b были взаимно простыми, необ­ходимо и достаточно, чтобы существовали такие целые числа m, п, что та + nb = 1.

  1. Пусть произведение 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. □

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

НОД(а,b1b2..bk)= 1.

  1. Пусть целые числа а1, а2, .... аl, b1, b2, .... bk таковы, что
    НОД(аi,bj)=1 для всех 1≤ il, 1≤ jk. Тогда НОД(a1a2..al,b1,b2...bk)=1.

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

Доказательство. Число а делится на b1 поэтому существует такое целое число с, что a = cb1.
Так как а делится на b2. то произведение cb1 делится на b2 Но по­скольку НОД(b1 b2) = 1, значит, по свойству 2 взаимно простых чисел, с делится на b2, то есть существует такое целое число d. что с = db2. Отсю­да а = cb1 = db1b2, то есть а делится на b1b2, □

  1. Если а делится на каждое из попарно взаимно простых чисел b1, b2,...bk, то а делится на произведение b1b2...bk.

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

  1. М делится на каждое из чисел а12, ....ak;

  2. если Mt — другое общее кратное чисел a1, а2,.... ak, то Mt делится на М.

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


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

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




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

  1. Положить r0a, r1← b, i ← 1.

  2. Найти остаток ri+1 от деления ri-1 на ri.

  1. Если ri+1=0, то положить dri. В противном случае положить i i + 1 и вернуться на шаг 2.

  2. Результат: d.

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


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

Download 1.44 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling