Определение Множество натуральных чисел
Download 1.44 Mb.
|
Символ Лежандра
Доказательство [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, причем 0≤r<d. Число r=y — qd является элементом множества А. поскольку у А и d А. Но d — наименьший неотрицательный элемент множества А, значит, r = 0 и y=qd. Таким образом, A={x d|xi }. Осталось доказать, что d — это наибольший общий делитель чисел a1, а2…ak. Каждое из этих чисел имеет вид 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 ≤ i≠j ≤ k. Взаимно простые числа обладают следующими свойствами. Для того чтобы целые числа а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. Пусть произведение 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. □ Если НОД(a,b1)=1, НОД(а,b2)=1, .... НОД(а,bk)=1, то НОД(а,b1b2..bk)= 1. Пусть целые числа а1, а2, .... аl, b1, b2, .... bk таковы, что НОД(аi,bj)=1 для всех 1≤ i≤ l, 1≤ j≤ k. Тогда НОД(a1a2..al,b1,b2...bk)=1. Пусть целое число а делится на b1 и на b2, НОД(b1 b2) = 1. Тогда a делится на произведение b1b2. Доказательство. Число а делится на b1 поэтому существует такое целое число с, что a = cb1. Так как а делится на b2. то произведение cb1 делится на b2 Но поскольку НОД(b1 b2) = 1, значит, по свойству 2 взаимно простых чисел, с делится на b2, то есть существует такое целое число d. что с = db2. Отсюда а = cb1 = db1b2, то есть а делится на b1b2, □ Если а делится на каждое из попарно взаимно простых чисел b1, b2,...bk, то а делится на произведение b1b2...bk. Определение 1.9. Целое число М называется наименьшим общим кратным целых чисел а1, а2,…,аk, аi≠0 для i=1, 2, .... k (обозначается М=НОК(a1, а2, .... ak)), если выполняются следующие условия: М делится на каждое из чисел а1,а2, ....ak; если Mt — другое общее кратное чисел a1, а2,.... ak, то Mt делится на М. Наибольший общий делитель и наименьшее общее кратное двух положительных целых чисел связаны соотношением: НОД(а, b) • НОК(а, b) = аb. 1.3. Вычисление наибольшего общего делителя 1.3.1. Алгоритм Евклида Для вычисления наибольшего общего делителя двух целых чисел применяется способ повторного деления с остатком, называемый алгоритмом Евклида. Алгоритм 1.1. Алгоритм Евклида. Вход. Целые числа а, b; 0 < b ≤ а. Выход. d=НОД (a, b). Положить r0 ← a, r1← b, i ← 1. Найти остаток ri+1 от деления ri-1 на ri. Если ri+1=0, то положить d←ri. В противном случае положить i ← i + 1 и вернуться на шаг 2. Результат: d. Сложность алгоритма Евклида равна O(log2a) Для доказательства корректности алгоритма Евклида нам понадобятся две леммы. Лемма 1.5. Если числа а и b целые и а делится на b, то b=НОД(а, b). Download 1.44 Mb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling