Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Топ:
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Интересное:
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Дисциплины:
2022-05-08 | 28 |
5.00
из
|
Заказать работу |
|
|
Пусть даны , и требуется найти их НОД. Пусть при этом . Разделим большее на меньшее с остатком . Затем второе на остаток, снова, возможно с остатком . Затем первый остаток на второй, получив остаток :
Этот процесс неизбежно остановится, так как при этих действиях монотонно уменьшаются, а множество натуральных чисел имеет наименьший элемент. Возможно, что окажется , тогда последнее равенство приобретает вид .
Теорема 5. Остаток , полученный при алгоритме Евклида, является: 1) общим делителем для
2) наибольшим среди общих делителей.
Доказательство.
Из последнего равенства видно, что делится на . Тогда из предпоследнего видно, что делится на , так как оба слагаемых делятся на .
Теперь, когда известно, что и делятся на , очевидно, что из равенства следует, что и тоже делится на . Продолжая таким образом подниматься всё выше, дойдём до того, что и делятся на .
А тогда и левые части первых двух равенств:
делятся на . Итак, общий делитель для .
2) Докажем, что это и есть наибольший общий делитель. Пусть = , но . Из первого равенства, , тогда , то есть если делятся на , то и делится на .
Далее, из второго равенства, , если и делятся на , то и делится на . Аналогично следуя далее, дойдём до того, что и делится на . Но тогда не наибольший общий делитель, а по условию, он наибольший. Значит, .
(Теорема 2). Если = , то существуют такие , что .
Рассмотрим другое доказательство, получающееся из алгоритма Евклида, и дающее возможность непосредственно найти .
(это построение называется расширенным алгоритмом Евклида).
Из предпоследнего, , то есть НОД есть линейная функция от . В свою очередь, из предшествующего ему, можно выразить , таким образом, НОД окажется выражен через :
|
.
Далее, поднявшись выше, можно выразить через , таким образом, окажется выражен через . В конце концов, будет выражен через , которые из двух первых равенств
выражены через . То есть, будет выражен через a,b как линейная комбинация, с коэффициентами u,v, состоящими из .
Если a делится на b без остатка, d=НОД(a,b) = b.
Пример. Для чисел найти НОД, а также представление (алгоритм Евклида и расширенный алгоритм Евклида).
Решение. Делим столбиком, последнее 50 на 5 делится без остатка.
Здесь .
Последний остаток равен 5.
Теперь выразим , начиная с предпоследнего уравнения.
, где , подставляем одно в другое,
= .
, .
Пример. Для чисел найти НОД, а также представление .
Решение.
Последний остаток равен 13.
= .
Проверка: .
Определение. Натуральное число, большее единицы, называется простым, если оно не имеет натуральных делителей кроме себя и единицы. Не простые числа называются составными.
(число 1 не относится ни к простым, ни к составным).
Примеры простых чисел меньше 100:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
ЛЕКЦИЯ 9. 11.03.2021.
Лемма 6. Всякое натуральное число, большее 1, делится по крайней мере на одно простое число.
Теорема 7. (Евклид). Каково бы ни было конечное множество простых чисел , всегда найдётся простое число, не принадлежащее этому множеству.
|
|
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!