О нахождении НОД и НОК по разложению.

Лемма. Если два числа представлены в виде разложений: ,  (где некоторые  или  могут быть равны 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.