Методические материалы учебно-методического комплекса по курсу «Теория чисел» (стр. 2 )

По теореме Эйлера: . Пример:, .

С помощью цепных дробей: , ,

Лекция 11

Неопределенные уравнения. .

Теорема. Пусть . Тогда 1) если не делит , то решений нет, 2) если , то существует бесконечное множество решений.

Теорема. . Пусть -частное решение. Тогда общее решение имеет следующий вид:

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

Системы сравнений. Пусть . Рассмотрим систему сравнений

(1)

и пусть

Если удовлетворяет системе, то и весь класс удовлетворяет системе. Определение решения системы сравнений.

Лекция 12

Теорема. Рассмотрим систему , . Если не делит , то система не имеет решений, если , то существует одно решение.

Обобщение: в случае системы из нескольких сравнений такого вида существует одно решение или система не имеет решений.

Китайская теорема об остатках. Пусть попарно взаимно простые числа и . Пусть -решение сравнения Тогда - решение системы сравнений .

Пример: .

Теорема Вильсона. Если - простое число, то .

Сравнения высшей степени по простому модулю.

Теорема. Сравнение высшей степени равносильно сравнению со старшим коэффициентом, равным 1.

Теорема. Сравнение -й степени при равносильно сравнению степени меньшей, чем .

Теорема. Сравнение -й степени имеет не более чем решений.

Сравнения по составному модулю.

Теорема. Пусть . Тогда сравнение равносильно системе сравнений (2)

Теорема. Пусть сравнения системы (2) имеют соответственно решений. Тогда сравнение (1) имеет решений.

Лекция 13

Сравнения вида . Вспомогательное сравнение . Строится последовательность приближений , так что выполняются условия для всех При этом должно выполняться условие не делит . Получим .

Задача: Решить сравнение

Здесь , где .

Рассмотрим многочлен . Его производная .

Решение сравнения будем искать методом последовательных приближений.

Сначала рассмотрим вспомогательное сравнение

Одним из его решений является , поэтому первым приближением будет . При этом ,

Следующее приближение ищем в виде . Параметр подбираем так, чтобы выполнялось условие .

Разлагаем по формуле Тейлора:

;

;

;

; , .

Следующее приближение ищем в виде так, чтобы выполнялось условие . Опять разлагаем по формуле Тейлора:

;

;

;

;

; , .

Ответ: (это одно из решений).

Лекция 14

Показатель класса. Определение . Пример: .

Теорема. .

Теорема. . Следствие. .

Теорема. .

Пример: последние цифры чисел : 7,9,3,1.

Теорема. .

Следствие 1. .

Следствие 2. Пусть . Количество степеней класса , имеющих такой же показатель , равно

Теорема. 1) Если , то классы являются некоторыми решениями сравнения ; 2) Если - простое число, то эти классы дают все решения этого сравнения.

Первообразные корни. Определение: .

Контрпример (), пример ().

Теорема. Если модуль – простое число, то первообразный корень существует. В этом случае количество первообразных корней равно .

Теорема. Первообразные корни по модулю существуют только для (-нечетное простое, >0. (без доказательства).

Лекция 15

Индексы. Определение. Контрпример ().

Таблица индексов ().

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

Теорема. Пусть - первообразный корень по модулю , и - взаимно просты с . Тогда

.

Теорема. Пусть - первообразный корень по модулю , и - взаимно просты с . Тогда

.

Следствие 1. .

Следствие 2. .

Двучленные сравнения по простому модулю. . Приводятся к виду , где не делит .

Теорема. Пусть . Тогда: 1) если не делит , то сравнение не имеет решений; 2) если делит , то существуют решений.

Определение. Вычет -ой степени по модулю .

Теорема. Вычеты -ой степени совпадают с вычетами степени .

Замечание. Сравнения и имеют разные решения.

Теорема. Число классов вычетов -ой степени равно .

Пример.

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

Определение. Корень -ой степени из .

Теорема. Все корни -ой степени из получаются из одного умножением на все корни -ой степени из .

Показательные сравнения. .

Пример: .

Лекция 16

Сравнения 2-ой степени по простому модулю (

.

Число решений равно 0 или 2: .

Определение: квадратичный вычет и невычет.

Пример: не имеет решений.

Критерий Эйлера. - квадратичный вычет, если и квадратичный невычет, если . Пример:

Теорема. Число классов квадратичных вычетов равно числу классов квадратичных невычетов и равно . Квадратичными вычетами являются классы чисел . Пример: .

Символ Лежандра. при не кратном .

Примеры: .

Свойства символа Лежандра:

1) ;

2) ;

3) Критерий Эйлера: ;

4) ;

5) ;

6) , где - количество чисел среди , имеющих отрицательный абсолютно наименьший вычет;

7)

Пример: может ли делиться на 29?

Ответ: нет, т. к. .

Лекция 17

Закон взаимности.

Лемма. Пусть и - нечетные простые числа.

Тогда .·

Функция .

Теорема (Закон взаимности). .

Следствие. если хотя бы одно из чисел и сравнимо с 1 по модулю 4, то , а если оба сравнимы с 3 по модулю 4, то.

Символ Якоби. -нечетное, -простые (м. б. одинаковые), . .

Свойства символа Якоби.

1) ;

2) ;

3) ;

Лемма. Если -нечетные, то , .

Следствие. , .

4) ;

5) ;

6) Закон взаимности. Если и - нечетные взаимно простые, то .

Приложение: Простые делители квадратичных форм.

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

Примеры:1);

2) ;

3) .

5.4. Темы практических занятий

1)  Теорема о делении с остатком.

2)  Простые и составные числа. Разложение на множители.

3)  НОД и НОК. Алгоритм Евклида.

4)  Функции [x] и {x}. Функция Эйлера.

5)  Конечные цепные дроби.

6)  Бесконечные цепные дроби. Разложение квадратичных иррациональностей в цепные дроби.

7)  Приближенные вычисления с помощью цепных дробей.

8)  Контрольная работа.

9)  Элементы теории сравнений. Теоремы Ферма и Эйлера.

10)  Признаки делимости.

11)  Полная и приведенная системы вычетов. Кольцо классов вычетов.

12)  Сравнения 1-ой степени.

13)  Неопределенные уравнения.

14)  Символ Лежандра. Первообразные корни и индексы.

15)  Сравнения 2-ой степени.

16)  Степенные и показательные сравнения.

17)  Итоговая контрольная работа.

5.5. Вопросы к коллоквиуму

Теорема о делении с остатком. Свойства делимости. Основная теорема арифметики. Простые числа. Теорема Евклида. НОК и НОД. Алгоритм Евклида. Взаимно простые числа и их свойства. Функция y = [x] и ее свойства. Цепные дроби. Подходящие дроби и их свойства. Бесконечные цепные дроби. Разложение действительного числа в цепную дробь. Периодические цепные дроби. Теорема Лагранжа о разложении квадратичной иррациональности в периодическую цепную дробь.

  11.  Приближение действительных чисел подходящими дробями.

  12.  Сравнения и их свойства.

  13.  Классы вычетов и операции над ними. Кольцо классов вычетов.

  14.  Полная и приведенная системы вычетов и их свойства.

  15.  Теорема Эйлера и теорема Ферма.

5.6. Примеры решения задач

1.  Теорема о делении с остатком

Задача №1.  Найти целые числа, дающие при делении на 7 частное 5.

Решение. Искомые числа можно представить в виде , где , т. е. может принимать значения 0,1,2,3,4,5,6. Поэтому искомыми числами являются 35,36,37,38,39, 40,41.

Ответ: 35,36,37,38,39, 40,41.

Задача №2.  Найти делитель и остаток, если делимое равно 25, а частное равно 3.

Решение. Из соотношений и следует двойное неравенство . Отсюда получаем границы для делителя: . Поэтому делитель может принимать значения 7 и 8, а остаток, соответственно, 4 и 1.

7 8 4 1

Ответ.

Задача №3.  Доказать, что сумма квадратов двух последовательных натуральных чисел при делении на 4 дает остаток 1.

Решение. Возьмем два последовательных натуральных числа и . Одно из них четное, а другое нечетное. Найдем сумму их квадратов: . Если разделить на 4, то в частном будет натуральное число , а в остатке 1.

2.  Простые и составные числа. Разложение на множители

Задача №4.  Найти натуральное число такое, что числа , , - простые.

Решение. Если , то при делении на 3 в остатке может быть 1 или 2. Если , то - не простое число, т. к. делится на 3. Если , то - также не простое число. Поэтому , , .

Задача №5.  Если - простое число, то его можно представить в виде или , где - натуральное число.

Решение. Разделим на 6 с остатком: . Поскольку простое число, то остаток не может быть равен 2, 3 и 4. Остаются две возможности: и . В первом случае , где , а во втором случае , где .

Задача №6.  Доказать, что среди чисел вида , где - простое число, только одно является точным кубом.

Решение. Данное число нечетное, поэтому оно является кубом нечетного числа: . Раскрывая это соотношение, получаем . Так как - простое число, то и .

Задача №7.  Доказать, что при между числами и содержится по крайней мере одно простое число.

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

Задача №8.  Доказать, что если натуральные числа при делении на дают остаток 1, то их произведение при делении на также дает остаток 1.