История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Топ:
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Оснащения врачебно-сестринской бригады.
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Интересное:
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Дисциплины:
2021-06-30 | 23 |
5.00
из
|
Заказать работу |
|
|
Изучим методы решения сравнений: ,
где .
Если удовлетворяет сравнению, то оно называется его решением.
Лемма. Если и , то , то есть всякое число, сравнимое с по модулю , тоже является решением сравнения.
Доказательство. означает, что .
, так как разность состоит из слагаемых вида , каждое из которых обязательно делится на , которое в свою очередь, делится на .
Не всякое сравнение разрешимо. Так, при малых можно проверить непосредственно: . Переформулируем иначе: Существует ли такое целое , что ?
Согласно лемме (см. выше), достаточно рассмотреть только 3 числа (в общем случае ).
,
,
.
Рассмотрим сравнения вида .
Теорема 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. При этом заметим, что
, то есть остаток . По условию, - это решение сравнения , то есть .
означает , где остаток делится на , значит, и , что и означает .
Следствие. Если - решения сравнения , то оно равносильно сравнению , где - некоторый многочлен степени с тем же старшим коэффициентом, который был у .
Теорема 3. Теорема Вильсона.
Число является простым .
Доказательство.
Необходимость. Пусть простое. Тогда по малой теореме Ферма, , то есть , то есть . Так как есть таких чисел , взаимно простых с , то сравнение имеет решений: .
Значит, .
Кроме того, было .
Рассмотрим разность: .
Если раскрыть скобки, получим многочлен степени меньшей, чем , и оно имеет решений. Это может быть, только если все коэффициенты делятся на , в частности свободный член уравнения, равный = . Однако среди простых чисел, больших 2, нет чётных, так что нечётное, а чётное, поэтому = .
Отдельно рассмотрим при , в том случае вид такой:
, что очевидно и так 0. Впрочем, .
Достаточность.
Пусть для числа верно ,и пусть оно не простое, , где . Тогда , т.е. .
Но в таком случае , значит, число присутствует в факториале:
, факториал делится на , но тогда должно быть и , что приводит к противоречию, так как 1 не делится на . Значит, такого числа не существует, и простое.
Примеры.
не делится на 4.
не делится на 6.
,
здесь вспомним признак делимости: .
|
и так далее.
Теорема 4.
Всякое сравнение степени равносильно некоторому сравнению степени не выше .
Доказательство.
По малой теореме Ферма, , тогда .
Поделим многочлен на с остатком: .
делится на по условию, первое слагаемое по малой теореме Ферма, значит, остаток делится на . Таким образом, можно перейти к сравнению , где степень многочлена .
Определение. Число называется квадратичным вычетом по модулю , если разрешимо сравнение: .
Теорема 5. Критерий Эйлера.
Число является квадратичным вычетом по простому нечётному модулю , и не является квадратичным вычетом .
Доказательство.
Лемма 1. Если - простое нечётное число, то возможны две ситуации: либо , либо .
Доказательство. Так как нечётное, то чётное, поэтому целое. Поделим на , и остаток обозначим через . Так как в этом случае , то , но по малой теореме Ферма , так что . Это значит, , то есть , таким образом, может быть сравнимым только с 1 или . Напомним, что это был остаток от деления на , так что сравнимо только с 1 или по модулю .
Лемма 2. Существует ровно квадратичных вычетов по простому нечётному модулю .
Доказательство. Рассмотрим все числа, взаимно простые с и меньшие чем , это . Возведём их в квадраты.
. Докажем, что .
, так как все слагаемые, кроме , делятся на . В таком случае, среди квадратов вторая половина даёт те же самые остатки, что и первая (симметрично, см. пример ниже), и существует не более чем квадратичных вычетов по модулю .
Допустим, что их меньше, то есть какие-то из этих вычетов совпадающие, . Но тогда , при этом как сумма, так и разность меньше и делиться на не может. Сумма, так как оба числа меньше половины , разность тем более. Противоречие, в итоге вывод, что совпадающих среди этих вычетов нет.
Пример. , рассмотрим чисел 1,2,3,4,5,6.
;
.
Вывод: только 1,2,4 могут быть квадратами чего-либо в поле вычетов . Это 3 числа, что как раз и равно .
эти 3 сравнения неразрешимы.
Итак,
; .
Рассмотрим теперь все и установим, какие из них сравнимы с 1, а какие с .
()
()
().
Кубы именно тех чисел, которые являются квадратами чего-либо, сравнимы с 1, другие с .
Доказательство. Теперь докажем критерий Эйлера, с учётом информации из двух лемм. Пусть является квадратичным вычетом по модулю , то есть существует , такое что . В этом случае , тогда, возводя в степень , получим: , а по малой теореме Ферма . Следовательно, из-за транзитивности .
|
Итак, любой квадратичный вычет является корнем уравнения степени . При этом ранее доказано, что существует разных квадратичных вычетов. Так как поле, то количество корней не может быть больше cтепени многочлена, и как раз эти квадратичных вычетов и являются корнями. Оставшиеся чисел и являются квадратичными невычетами, для них .
|
|
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!