Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Топ:
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Интересное:
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Дисциплины:
2021-06-30 | 33 |
5.00
из
|
Заказать работу |
|
|
Лемма. Если два числа представлены в виде разложений: , (где некоторые или могут быть равны 0, если соответствующего простого числа нет в разложении), то
НОД (a,b) = , где ,
НОК (a,b) = , где .
Лемма. НОД (НОД (a,b),c)= НОД (a,b,c).
Доказательство.
делит , которое делит , значит, делит .
Если не наибольший, и существует , на который, в свою очередь делятся все эти числа , то , противоречие.
Пусть , тогда .
Пусть , тогда = =
. Итак, если , значит, существует разложение .
Взаимно простые числа: в совокупности и попарно.
Числа называются взаимно простыми в совокупности, если не существует , которое делит все .
Числа называются попарно взаимно простыми, если для каждой пары , их НОД равен 1.
Если числа попарно взаимно просты, то они взаимно просты в совокупности, обратное неверно.
Пример. 6,10,35.
НОД (6,10) = 2, НОД (10,15) = 5, НОД (6,15) = 3.
Общего делителя, на который бы делились все 3 числа, не существует.
НОД (a,b) взаимно прост с c, НОД (a,b,c) = 1.
Пересечение каждой пары множеств непусто, а пересечение всех трёх пустое множество.
Лемма. О вынесении общего множителя за знак НОД.
Пусть . Тогда .
Доказательство. .
Теорема. (О взаимосвязи НОД и НОК).
, т.е. .
Доказательство 1. Разложим a,b в произведение простых множителей, НОК определяется объединением, НОД пересечением. По формуле включений и исключений, . Когда делим на пересечение, то этим самым исключаем множители, входящие в НОД, ведь в произведении они изначально учитываются по два раза.
ЛЕКЦИЯ 10. 13.3.2021.
Доказательство 2. Во-первых, является общим кратным для : делится на , делится на .
Покажем теперь, что это именно наименьшее общее кратное. Пусть существует ещё одно кратное, , .
|
Тогда . Пусть . Тогда .
делит левую часть этого равенства, но оно взаимно просто с , поэтому делит . Тогда . Тогда , то есть наименьшее общее кратное.
Признаки делимости на 2,3,4,5,6,7,8,9.
Пусть число в десятичной записи имеет вид , т.е. .
(последняя цифра), (число, получающееся вычёркиванием последней цифры, т.е. ).
. В этом случае верны признаки делимости на (необходимые и достаточные условия):
Условие | |
2 | (последняя цифра 0,2,4,6,8). |
3 | |
4 | |
5 | (последняя цифра 0 или 5) |
6 | делится на 2 и 3. |
7 | , , |
8 | |
9 |
Докажем все эти признаки.
Для 2 и 5.
Наиболее просто установить делимость на 2 или 5. Так как , а делится на 2 и на 5, то делимость на 2 или 5 эквивалентна делимости на 2 или 5.
Для 3 и 9.
, вычтем , получится число вида , которое делится и на 3, и на 9. Поэтому делимость на 3 или 9 эквивалентна делимости суммы цифр на то же самое.
n = s + m где s делится на 3, в этом случае делимость n и m экв.
Для 4. Число кратно 100, поэтому делится на 4. Разность между ним и равна , делимость этого числа на 4 эквивалентна делимости на 4.
= , где первая компонента делится на 4, поэтому делимость на 4 эквивалентна .
Для 6. Очевидно, объединение двух свойств делимости, на 2 и 3: последняя цифра чётная и сумма цифр делится на 3.
Для 7. , где первое слагаемое делится на 7, тогда делимость числа на 7 эквивалентна .
То есть, нужно записать число без последней цифры, утроить его и прибавить . Мы получаем меньшее число, по которому вывод сделать легче.
Но наилучший признак это (число без последней цифры, вычесть удвоенную последнюю цифру). Это сильно уменьшает исследуемое число, в 10 раз, причём можно делать несколько шагов, пока не получим какое-нибудь двузначное число, делимость которого на 7 легко выясняется.
Докажем его. Рассмотрим .
Так как , то делимость эквивалентна делимости .
При этом , но так как 10 не делится на 7, то делимость целиком зависит от множителя , что и требовалось доказать.
|
Для доказательства признака нужно аналогичным образом рассмотреть .
Примеры.
Выяснить, делится ли на 7 число .
= = . 21 делится на 7, поэтому 399 тоже.
Выяснить, делится ли на 7 число .
1) = .
2) .
3) , делится на 7.
Для 8. Так как 1000 делится на 8 (частное 125), то для делимости на 8 достаточно проверять число, состоящее из последних 3 цифр, то есть = .
= , где первое слагаемое делится на 8, поэтому делимость на 8 эквивалентна .
Остатки и сравнимость по модулю. Вспомним из 1 семестра:
Определение. Два целых числа называются сравнимыми по модулю n, если при делении на n они дают одинаковые остатки, т.е. если их разность делится на n: . Обозначается .
Таким образом, множество распадается на n непересекающихся классов. - класс вычетов по модулю n.
означает, что .
Свойства сравнимости.
1. . Рефлексивность
2. . Симметричность
3. и . Транзитивность
Свойство 4. и
Свойство 5. и
(Доказывали в 1 семестре, когда вводили понятие кольца вычетов).
Следствие из свойства 5. .
Пример. 6 и 11, в квадрате 36 и 121, остатки от деления на 5 всё равно 1.
|
|
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!