Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Топ:
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Интересное:
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2021-06-30 | 37 |
5.00
из
|
Заказать работу |
|
|
ЛЕКЦИЯ 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. Впрочем, .
Достаточность.
Пусть для числа вер
|
|
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!