Теорема 9. (Основная теорема арифметики).

ЛЕКЦИЯ 9. 11.03.2021.

 

Лемма 6. Всякое натуральное число, большее 1, делится по крайней мере на одно простое число.

Доказательство. Пусть . Если оно простое, то лемма верна, так как делится на себя (т.е. на простое). Если оно не простое, то оно делится на какое-то другое натуральное число, обозначим его . Если  простое, лемма доказана. Если  не простое, значит, оно делится на какое-то число , и т.д.   поэтому процесс оборвётся через конечное число шагов, и последнее  должно быть простым, а не единицей, так как если  и  не простое, то оно делится на какое-то , значит, между  и 1 в этой последовательности было бы ещё какое-то число.

 

Теорема 7. (Евклид).     Каково бы ни было конечное множество простых чисел , всегда найдётся простое число, не принадлежащее этому множеству.

Доказательство. Рассмотрим число . В силу прошлой леммы, оно делится на некоторое простое число . Но это простое число не может совпадать ни с одним из простых чисел , иначе бы 1 делилась на какое-то , как разность двух чисел, делящихся на . Таким образом, существует какое-то ещё одно простое число, кроме этих, либо само  простое.

Примеры.

,  простое.

, , делится на 2, т.е. если  содержит на все по порядку начиная с меньшего, то  не обязательно простое, но делится на какое-то простое, не входящее в это множество.  

Предложение 8. Если произведение нескольких целых чисел делится на простое число, то на него делится хотя бы один из сомножителей.

Доказательство.

Докажем методом индукции по числу сомножителей .

1) база индукции. Пусть . Пусть . Если , то доказано. Если не делится, то . Тогда по следствию 4, . 

2) Индукционный шаг. Допустим, что этот факт верен для  сомножителей. Пусть . Рассмотрим  исходных и новый как 2 сомножителя.

. Тогда либо , либо . Если последний не делится на , то произведение  прочих делится, а для  уже доказано, что если это произведение делится, то хотя бы один из сомножителей делится на .

 

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

Лемма. Если два числа представлены в виде разложений: ,  (где некоторые  или  могут быть равны 0, если соответствующего простого числа нет в разложении), то

НОД (a,b) = , где , 

НОК (a,b) = , где .   

 

 

Лемма. НОД (НОД (a,b),c)= НОД (a,b,c). 

Доказательство.

 делит , которое делит , значит,  делит . 

Если  не наибольший, и существует , на который, в свою очередь делятся все эти числа , то , противоречие. 

 

Пусть , тогда .  

Пусть , тогда  =  =

. Итак, если , значит, существует разложение .  

 

ЛЕКЦИЯ 10. 13.3.2021.

Доказательство 2. Во-первых,  является общим кратным для :  делится на ,  делится на . 

Покажем теперь, что это именно наименьшее общее кратное. Пусть существует ещё одно кратное, , .

Тогда . Пусть . Тогда .  

 делит левую часть этого равенства, но оно взаимно просто с , поэтому делит . Тогда . Тогда , то есть  наименьшее общее кратное. 

 

 

Для 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.

 

Доказательство.

 =

 + ,  

при этом , то есть . Второе слагаемое делится на , тогда остаток от деления первого такой же, как и от деления числа  на . 

 

Пример. Выяснить, делится ли 1365 на 13.

 

(рассм. 65,78,91,104)

(рассм. 130, 650, 780, 910, 1040, 1001). 

 = ,

проверка: . 

 

* Совершенные числа (ознакомительно).

Число называется совершенным, если оно равно сумме всех своих собственных делителей. Например, , .

Следующие числа 496, 8128,

До сих пор неизвестно, есть ли нечётные совершенные числа.

Если совершенное число чётно, то оно имеет вид , где  простое. 

, ,  . 

, ,  . 

, , не простое. 

, , . 

,  не простое.

,  . . 

 

ЛЕКЦИЯ 11. 18.3.2021.

 

Теорема 1. Если ,  - полная система вычетов по модулю , то числа вида  тоже есть полная система вычетов по модулю .

(При линейном преобразовании ax+b числа из разных классов вычетов не попадут в один класс, если a взаимно прост с m).  

Доказательство.

Докажем, что если  в различных классах вычетов, то  тоже. Если   не делится на , то

 =  тоже не делится, так как .

Обозначим  - число вычетов, взаимно простых с , получится так наз. «приведённая система вычетов». 

 

Функция Эйлера.  - количество натуральных чисел, не превышающих  и взаимно простых с .

Для простого числа , , так как множество чисел, с которыми НОД равен 1, это следующее множество: .  

Теорема 2. Если ,  - приведённая система вычетов по модулю , то  тоже образуют приведённую систему вычетов по модулю . 

Доказательство. Если допустить что  то

, но  не делится на , значит , противоречие, ведь тогда , а это была приведённая система вычетов.

Пример.

1,3,5,7 взаимно просты с .  Умножим на .

Получим 3,9,15,21. Исследуем остатки при делении на 8.

, , , .

Множество остатков получилось то же самое: 1,3,5,7, но в другом порядке.

Если умножить на 2, не взаимно простое с 8:

2,6,10,14. Остатки: 2,6,2,6 есть повторы, т.к. нарушено условие .

 

Пример.

1,2,3,4,5,6 взаимно просты с . Возьмём . Умножим:

Получим 5,10,15,20,25,30. Исследуем множество остатков: 

, , , , , .

(как перестановка (5,3,1,6,4,2)).

 

Теорема 3. Теорема Эйлера. .   

Доказательство.    Пусть  - приведённая система вычетов по модулю , тогда  тоже образуют приведённую систему вычетов по модулю . Тогда существует какая-то перестановка , такая, что:

, ,..., . 

Сравнения можно умножать (было свойство), тогда

, где в больших скобках одно и то же число, отличается лишь порядок множителей.  

. 

Пример. Найти остаток от деления  на 7. 

Заметим, что , тогда , и , т.е. .  

 =  = , тогда . 

Ответ: остаток равен 4, а число  делится на 7.

Аналогично, ,  тоже делятся на 7.

 

Теорема 4 (малая теорема Ферма).

Для любого простого числа  и , . 

Доказательство.    Пусть , тогда по теореме Эйлера , что означает , тогда .

Пусть , но  простое, тогда , тогда , тогда и , что и означает . 

Замечание. Отличие т.Ферма от теоремы Эйлера:

1) вместо m простое p,   

2) число а не должно быть взаимно простым с p. 

Мы уже знаем, что . Теперь рассмотрим, чему равно ,...,  . 

Лемма. .

Доказательство. Для : построим квадратную матрицу из чисел: 

не взаимно просты с  только числа: , это  чисел.

Таким образом, . 

Для  можно построить не квадратную, а кубическую матрицу, где не взаимно просты с  числа будут только в 2-мерном слое, который состоит из   чисел. Таким образом, .

Аналогично, . 

Рассмотрим функцию Эйлера произведения двух взаимно простых чисел. Сначала наиболее понятный случай, пусть это будут два простых числа . (Они очевидно, взаимно просты).

Лемма. Пусть  - два простых числа. Тогда . 

Доказательство.

Все числа от 1 до  можно записать в виде прямоугольной матрицы:

из которой видно, что не взаимно простых с  есть всего  чисел:

.  

Если сделать по  элементов в строке, то аналогично получится, что найдём  чисел, не взаимно простых с : .

В пересечении этих двух множество лишь одно число . По формуле включений-исключений, чисел, взаимно простых с :

 =  = . 

 

- - - Перерыв - - -

 

Теорема 5. Функция Эйлера мультипликативна, т.е. если  то .  

Доказательство (чуть ниже).

Пример. ,  (все чётные и все кратные 3 не взаимно просты с 12, остальные отмечены красным). 

 1 2 3

 4 5 6

 7 8 9

10 11 12

Доказательство.

Пусть  взаимно простые числа (но не обязательно простые).

Рассмотрим полную систему вычетов по модулю :

Здесь каждая строка - полная система вычетов по модулю , а каждый столбец - полная система вычетов по модулю :

  (см. теорему 1).

Пусть  (в первой строке  таких чисел). Тогда весь -й столбец тоже обладает свойством , иначе, учитывая  было бы . Итак, есть  столбцов по   чисел, где все числа взаимно просты с . Но каждый столбец представляет собой полную систему вычетов по модулю , значит, в каждом столбце  чисел, взаимно простых с . Итак,  столбцов, где числа взаимно просты с , и в каждом по  чисел, взаимно простых с . Итого  чисел, взаимно простых с ,  одновременно. Теорема доказана.

Примечание. В разных столбцах множество чисел может быть со сдвигом, то есть это не обязательно подматрица из  столбцов и строк. В примере выше показано это (где числа выделены красным).

 

Теорема 6. О вычислении функции Эйлера

Пусть  - разложение числа в произведение степеней простых сомножителей, тогда .

Доказательство.

Пусть . Из-за мультипликативности функции Эйлера,

. Кроме того, выше мы доказали лемму, что . Тогда  = , если вынести за скобку каждое , то они как раз и образуют  за скобками:

  = . 

Пример. Найти количество чисел, не превышающих 36 и взаимно простых с 36.  

Решение. 36 = , тогда  =

 =  = .  

Столбцы под чётными должны исключить (2,4,6), и под кратными 3, т.е. 3,6-й.   Остаются 2 столбца по 6 чисел, то есть 12 чисел: 

1 2 3 4 5 6

7 8 9 10 11 12

13 14 15 16 17 18

19 20 21 22 23 24

25 26 27 28 29 30

31 32 33 34 35 36

Теорема 1.

1) Если , то сравнение  имеет решение, причём единственное.

2) Если ,  и  не делится на , то сравнение  неразрешимо.

3) Если , и , то сравнение  имеет  решений.

Доказательство.

1) Пусть  полная система наименьших неотрицательных вычетов по модулю , среди них есть одно число, сравнимое с : . Но  тоже полная система вычетов (теорема 1 см. в прошлом §). Тогда среди них есть ровно одно число, сравнимое с  из множества , и тогда .  

 

2) Пусть . Тогда . Пусть сравнение разрешимо, тогда , т.е. , противоречие с тем, что  не делится на . 

Пример.   НОД (a,m)= 5.

, неразрешимо: 5x (напр, 5,10,15,20,…) не дают остаток 8 при делении на 10.

 

3) , и при этом , т.е. . 

, сократим на .  

Здесь уже вынесли НОД, т.е. как в п.1.  , значит, это сравнение имеет единственное решение, . Оно же является решением и для сравнения , так как  

. 

Перейдём к сравнениям по модулю . Есть  чисел вида , меньших , они попарно несравнимы по модулю   (все меньше чем ) и тоже являются решениями для . 

, добавляется величина, содержащая . 

 

Что этот п.3 в теореме означает, простыми словами на примере:

Пример. , НОД чисел  равен 2, и среди чисел  есть 2 числа, таких что  делится на 6 с остатком 4. 

Это 2 и 5. Результаты 4 и 10. Пара чисел, т.к. d=2.

 

 

ЛЕКЦИЯ 12. 20.3.2021.

 

Пусть , рассмотрим сравнение .

Если  то b можно перенести влево и вычесть из .

Теорема 2.  Если  - решение сравнения , то это сравнение равносильно , где  - неполное частное от деления  на . 

Доказательство.

 , где остаток  степени, меньшей чем 1, ведь делили на многочлен  степени 1. При этом заметим, что

, то есть остаток . По условию,  - это решение сравнения , то есть .  

 означает  , где остаток делится на , значит, и , что и означает . 

Следствие. Если  - решения сравнения , то оно равносильно сравнению , где  - некоторый многочлен степени  с тем же старшим коэффициентом, который был у . 

 

Доказательство.

Необходимость. Пусть  простое. Тогда по малой теореме Ферма, , то есть , то есть . Так как есть   таких чисел , взаимно простых с , то сравнение  имеет  решений:  . 

Значит, . 

Кроме того, было .

Рассмотрим разность: .

Если раскрыть скобки, получим многочлен степени меньшей, чем , и оно имеет  решений. Это может быть, только если все коэффициенты делятся на , в частности свободный член уравнения, равный  = . Однако среди простых чисел, больших 2, нет чётных, так что  нечётное, а  чётное, поэтому  = . 

Отдельно рассмотрим при , в том случае вид такой:

, что очевидно и так 0. Впрочем, .

Достаточность.

Пусть для числа  вер