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

Решение. Составляем неопределенное уравнение , где и - количества марок 1-го и 2-го типов соответственно. Находим частное решение: Общее решение имеет вид

,.

По смыслу задачи неизвестные и должны быть неотрицательны. Это дает двойное неравенство для переменной : . Целочисленная переменная принимает значения . Им соответствуют решения уравнения

,

,

.

Ответ: ; ; .

Задача №35.  Найти все числа, на которые может быть сократима дробь . При каких значениях числа дробь будет сократимой?

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

Ответ: Дробь может быть сократима только на 11 при

10.  Первообразные корни и индексы

Задача №36.  Найти первообразный корень по модулю 17.

Решение. Проверим число 2:

Это означает, что показатель числа 2 по модулю 17 равен 8, и число 2 не является первообразным корнем по модулю 17.

Проверим число 3:

Показатель числа 3 по модулю 17 равен 16, поэтому число 3 является первообразным корнем по модулю 17.

Задача №37.  На циферблате часов расставить числа 1,2,3,…,12 так, чтобы для любых трех чисел , стоящих подряд, число делилось на 13.

Решение. Число 13 – простое. Возьмем любой первообразный корень по модулю 13, например 2. Выпишем его двенадцать степеней:

2,4,8,16,32,64,128,256,512,1024,2048,4096.

Это геометрическая прогрессия. По свойству геометрической прогрессии квадрат любого члена равен произведению двух соседних членов: . Если числа прогрессии заменить их остатками при делении на 13:

2,4,8,3,6,12,11,9,5,10,7,1,

то полученная последовательность будет удовлетворять условию задачи. Эти числа можно расставить на циферблате начиная с любого места. Кроме того, можно двигаться как по часовой стрелке, так и против часовой стрелки.

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

Задача №38.  Решить сравнение .

Решение. Число 2 является первообразным корнем по модулю . Составим таблицу индексов по модулю 11 и основанию 2.

	1	2	3	4	5	6	7	8	9	10
	0	1	8	2	4	9	7	3	6	5

Проиндексируем данное сравнение и получим новое сравнение по модулю . Введём новую переменную :

,

,

,

,

.

По таблице индексов находим .

Ответ: .

Задача №39.  Решить показательное сравнение .

Решение. Проиндексируем данное сравнение, воспользовавшись таблицей индексов из предыдущего примера:

Ответ: .

Задача №40.  Решить сравнение .

Решение. Преобразуем сравнения путем замены коэффициентов на другие, сравнимые с ними по модулю 13:

Таким образом, сравнение имеет два решения.

Ответ: .

12.  Символ Лежандра

Задача №41.  Вычислить символ Лежандра .

Решение. Воспользуемся свойствами символа Лежандра:

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

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

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

Это означает, что число 5 является квадратичным невычетом по модулю 17, поэтому сравнение не имеет решения.

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

Решение. Допустим, что . Тогда . Отсюда получаем . Числа и взаимно просты с . Возьмем число такое, что . Тогда . Это означало бы, что число (-1) является квадратичным вычетом по модулю . Но значение символа Лежандра для числа (-1) равно , т. е. (-1) является квадратичным невычетом по модулю .

Задача №44.  Числа и можно представить в виде суммы квадратов двух целых чисел. Доказать, что их произведение также можно представить в виде суммы квадратов двух целых чисел.

Решение. Пусть и . Тогда

Задача №45.  Доказать, что число является суммой квадратов двух целых чисел, где - целые числа.

Решение следует из предыдущей задачи применением метода математической индукции.

5.7. Варианты экзаменационных билетов

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 1

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

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

3.  Найти количество натуральных чисел, не превосходящих 1800 и взаимно простых с 44.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 2

1.  Свойства делимости.

2.  Неопределенные уравнения 1-ой степени.

3.  Решить показательное сравнение

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 3

1.  Основная теорема арифметики.

2.  Системы сравнений 1-ой степени. Китайская теорема об остатках.

3.  Найти показатель, которому принадлежит число 9 по модулю 17.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 4

1.  Простые числа. Теорема Евклида.

2.  Закон взаимности для символа Лежандра.

3.  Разложить число в цепную дробь.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 5

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

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

3.  Найти две последние цифры числа .

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 6

1.  Взаимно простые числа и их свойства.

2.  Решение показательных сравнений.

3.  Разложить в бесконечную цепную дробь число .

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 7

1.  Функция y = [x] и ее свойства.

2.  Первообразные корни. Существование первообразного корня по простому модулю.

3.  Найти число, представимое цепной дробью <3,7,2,1,4>, и подходящие дроби.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 8

1.  Цепные дроби. Подходящие дроби и их свойства.

2.  Индексы и их свойства.

3.  Решить систему сравнений

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 9

1.  Бесконечные цепные дроби. Разложение действительного числа в цепную дробь.

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

3.  Найти с помощью алгоритма Евклида НОД чисел 4121 и 1469, а также их НОК.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 10

1.  Периодические цепные дроби. Теорема Лагранжа о разложении квадратичной иррациональности в периодическую цепную дробь.

2.  Теорема Вильсона.

3.  Решить сравнение

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 11

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

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

3.  Найти первообразный корень по модулю 17 и составить таблицу индексов.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 12

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

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

3.  Решить неопределенное уравнение

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 13

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

2.  Показатель и его свойства.

3.  Решить сравнение

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 14

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

2.  Двучленные сравнения n-ой степени по простому модулю.

3.  Решить сравнение

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 15

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

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

3.  Вычислить символ Лежандра .

6.1. Рекомендуемая литература

а) основная литература:

Нестеренко чисел: учебник для студентов высших учебных заведений.

М.: Издательский центр «Академия», 20с.

б) дополнительная литература:

Виноградов теории чисел. — Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2003, 176 стр.

Бухштаб чисел. - М.: Просвещение, 19с.

Сушкевич чисел. Элементарный курс. Харьков: ХГУ, 19с.

Задачи и упражнения по теории чисел. Методическая разработка. Ч.1,2. Составители: , . - г. Горький, ГГУ, 1986.

в) программное обеспечение и Интернет-ресурсы:

http://eek. diary. ru/p.html

На этом сайте много учебников по теории чисел.

7. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

Компьютерный класс с доступом к Интернету

8. КРИТЕРИИ ОЦЕНОК

Оценка	Уровень подготовленности
отлично	Подготовка, уровень которой существенно выше среднего
хорошо	Хорошая подготовка с некоторыми ошибками
удовлетворительно	Подготовка, удовлетворяющая минимальным требованиям
неудовлетворительно	Необходима дополнительная подготовка

Сергей Андреевич Тюрин

Методические материалы

учебно-методического комплекса по курсу

«Теория чисел»

Учебно-методическое пособие

Федеральное государственное автономное образовательное учреждение

высшего образования

«Нижегородский государственный университет им. ».

Нижний Новгород, пр. Гагарина, 23