Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Теорема о линейном представлении наибольшего общего делителя
Теорема. Если то существуют целые числа и и v, для которых Доказательство: Рассмотрим множество всех целых чисел вида где х и у - любые целые числа Это множество не пусто, в частности, ему принадлежат числа а и b. Ведь а можно представить в виде а b - в виде Для любых двух целых чисел из этого множества частное от деления одного на другое также принадлежит множеству М. Действительно, если то Пусть - наименьшее положительное число в множестве М. Тогда любое число из М делится на число без остатка. Действительно, остаток должен принадлежать множеству М и должен быть меньше , а этому условию удовлетворяют лишь остатки, равные нулю. Таким образом, и а, и b делятся на без остатка, т.е. – их общий делитель. Очевидно, что делится на любой другой их общий делитель, а это означает, что ■
Пример. Найти линейное представление наибольшего общего делителя чисел 1173 и 323. Решение: Из примера, приведенного в предыдущем параграфе, известно, что НОД(1173, 323) = 17. Будем подниматься по равенствам алгоритма Евклида вверх: Ответ: НОД
Теорема Евклида. Если ас делится на b, с и b взаимно просты, то а делится на b. Доказательство: Так как то по теореме о линейном представлении НОД существуют числа и и v, для которых Тогда Из условия следует, что слагаемое аси делится на b, слагаемое ab n также делится на b. Отсюда, а делится на b. Что и требовалось доказать. ■
Date: 2015-07-02; view: 14488; Нарушение авторских прав |