Конспект лекций по курсу «теория чисел»

Скачать 185.62 Kb.

Название	Конспект лекций по курсу «теория чисел»
	Н И Лобачевского
Дата	02.03.2013
Размер	185.62 Kb.
Тип	Конспект лекций

Министерство образования и науки Российской Федерации

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

им. Н.И. Лобачевского

Управление

филиалов

университета

Выпуск №1

КОНСПЕКТ ЛЕКЦИЙ ПО КУРСУ

«ТЕОРИЯ ЧИСЕЛ»

Методическая разработка

Нижний Новгород

2010

УДК 511.17 Конспект лекций по курсу «Теория чисел». Методическая разработка / Составитель Тюрин С.А. - Н.Новгород: ННГУ, 2010. – 19 с.

Рассмотрены следующие разделы теории чисел: теория делимости, простые и составные числа, НОД и НОК, числовые функции, цепные дроби, теория сравнений, кольцо классов вычетов, решение сравнений, первообразные корни и индексы, сравнения 2-й степени, символ Лежандра, закон взаимности.

Для студентов механико-математического факультета.

Составитель: Тюрин С.А.

Рецензент: доцент кафедры

геометрии и высшей алгебры ННГУ

Разуваев А.Г.

 Нижегородский государственный

университет им. Н.И. Лобачевского,

2010 г.

Лекция 1

Теорема о делении с остатком. а>0, a=0, a<0. Единственность. Делимое, делитель, частное, остаток.
Делитель, кратное. Теорема: b>0 – делитель т. и т.т. когда остаток равен нулю. Обозначение: b|a.
Свойства делимости. 1) a|a 2) 1|a 3) b|a±b|±a 4) c|b, b|ac|a

5) b|a, k≠0kb|ka 6) kb|ka, k≠0b|a 7) b|ab|ac 8) c|a, c|bc|a±b

9) c|a₁, c|a₂, ..., c|a_n c|a₁b₁+a₂b₂+...+a_nb_n

10) b₁|a₁, b₂|a₂, ..., b_n|a_nb₁b₂...b_n|a₁a₂...a_n 11) b|abⁿ|aⁿ

Простое число. Составное число.

Теорема. Наименьший положительный делитель не равный 1 – простое число.

Теорема. Любое натуральное число большее 1 является либо простым, либо произведением простых.

Основная теорема арифметики. Любое натуральное число большее 1 раскладывается на простые множители единственным образом.

Каноническое разложение натурального (целого) числа.

Теорема. p-простое, p|abp|a или p|b.

Теорема о разложении на простые множители делителя натурального. числа.

Теорема Евклида. Множество простых чисел бесконечно.

Лекция 2

Решето Эратосфена.

Теорема. Если натуральное число n>1 не делится ни на одно простое, не превосходящее

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

Теорема. Если в множестве [2,N] вычеркнуть все числа, кратные первым r простым числам, то первое незачеркнутое число – простое. Алгоритм нахождения простых чисел.

Общее кратное. Примеры. НОК. Теорема. Любое общее кратное делится на наименьшее общее кратное. Обозначение НОК: [a₁,a₂,…,a_n]
Общий делитель. Единица является ОД. Множество ОД – конечно. Определение: НОД – это такой ОД, который делится на все ОД. Обозначение НОД: (a₁,a₂,…,a_n).

Теорема. Для любых натуральных чисел a₁,a₂,…,a_n существует НОД. (Для доказательства надо взять НОК всех ОД)

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

Теорема: d=(a₁,a₂,...,a_n)d является ОД и числа {a₁/d, a₂/d, ...a_n/d} –

взаимно простые.

Теорема. 1) Если (a₁,a₂,...,a_n)=d, то (ka₁,ka₂,...,ka_n)=kd;

2) Если k=ОД, то (a₁/k, a₂/k,...,a_n/k)=d/k.

Теорема. Пусть m=[a,b], d=(a,b). Тогда md=ab.

Замечание. Для трех чисел это неверно.

Следствие. a и b взаимно просты  [a,b]=ab.

Нахождение НОД и НОК нескольких натуральных чисел.

Лемма. a=bлюбой делитель одного числа является делителем

второго и наоборот.

Теорема. (a₁,a₂,...,a_n)=((a₁,a₂,...,a_n-1),a_n).

Аналогичная теорема справедлива и для НОК.

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

1) Если a и c – взаимно простые числа и c|ab, то c|b.

2) Если a и c – взаимно простые числа, то (ab,c)=(b,c).

3) Если a и c – взаимно простые числа и b и c – взаимно простые числа, то ab и c – взаимно простые числа.

Нахождение НОК и НОД разложением на простые множители.
Алгоритм Евклида.

Лекция 3

Свойство НОД. Теорема. a,b u,vZ такие, что au+bv=d – НОД
Следствие. (a,b)=1u,vZ такие, что au+bv=1.

Целая часть действительного числа.

Определение [x]. Наибольшее целое число, не превосходящее x. n≤x
Теорема. Пусть x>0, xR, dN. Количество натуральных чисел, кратных d и не превосходящих x, равно [x/d].
Теорема. [x/d]=[[x]/d]. Следствие. [x/mn]=[[x/m]/n].
Теорема. Пусть nN и p- простое число. Тогда показатель кратности, с которым число p входит в разложение n!, равно [n/p]+[n/p²]+[n/p³]+... . Пример: p=5, n=50, k=12.
Числовые функции. Количество делителей (n), (20)=6.

Теорема. Если n=p₁^k₁p₂^k₂...p_s^k_s, то (n)=(k₁+1)(k₂+1)...(k_s+1).

, (20)=42.

Теорема.

.

Совершенные числа. Примеры: 6,28. Проблема существования нечетных совершенных чисел. Вид четных совершенных чисел:

, если в скобке стоит простое число.

Функция Эйлера (n). Вид (p), (pⁿ).

Мультипликативные и вполне мультипликативные функции.

Примеры: 1) (n), (n) 2) n^ 3) (n)- без доказательства.

Числовой интеграл.

.

Теорема. Если f – мультипликативна, то и F – мультипликативна, причем

.

Примеры числовых интегралов: 1) 1 2) n 3)

Формула Гаусса

.

Лекция 4

Цепные дроби. Определение. Запись . Длина цепной дроби.

Цепная дробь – рациональное число. Пример: <2,7,3>=47/22.

Теорема. Любое рациональное число может быть представлено

конечной цепной дробью. Пример: 73/34=<2,6,1,4>.

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

единственно.

П
Теорема. .

одходящие дроби для цепной дроби .

Рекуррентные последовательности

Таблицы для вычисления подходящих дробей.

Свойства подходящих дробей

;

2) Несократимость подходящих дробей;

3)

;

4) Знаменатели подходящих дробей возрастают:

;

5)

;

6) Дроби с четными номерами возрастают, с нечетными убывают;

7) Из двух соседних дробей дробь с четным номером меньше;

8) Любая дробь с четным номером меньше любой дроби с нечетным номером;

9) Расстояния между соседними подходящими дробями уменьшаются.

Бесконечные цепные дроби

Теорема Существует предел последовательности подходящих дробей.

Определение БЦД (бесконечной цепной дроби):

Полное и неполное частные БЦД: .

Теорема

.

Теорема

.

Лекция 5

Теорема. Любое иррациональное действительное число может быть разложено в БЦД.

Теорема. Разложение иррационального числа в БЦД единственно.

Квадратичная иррациональность. Пример и контрпример.
Периодическая БЦД.

Определение.

Критерий периодичности:

Теорема. Любая периодическая БЦД есть квадратичная иррациональность.

Нахождение квадратного уравнения для периодической БЦД.

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

Пример:

Приближение иррациональных чисел подходящими дробями.

Лекция 6

Наилучшие приближения действительных чисел.

Определение:

- наилучшее приближение к

, если

Теорема. Пусть

. Тогда ближайший из концов интервала является наилучшим приближением к

.

Теорема. Любая подходящая дробь является наилучшим приближением к

Применения цепных дробей: 1) Зубчатые колеса; 2) Календарный стиль: юлианский и грегорианский календарь.
Сравнения. Определение и примеры.

Теорема.

имеют одинаковые остатки при делении на

Свойства сравнений:

1) рефлексивность;

2) симметричность;

3) транзитивность;

4)

;

5)

;

6)

;

7)

;

8) Сложение и вычитание сравнений;

9) Умножение сравнений;

10) Возведение в степень;

11) Если

;

12) Перенос слагаемых с изменением знака;

13)

;

14)

множество общих делителей

совпадает с множеством общих делителей

;

15)

, где

- НОК

.

Лекция 7

Классы вычетов. Определение, обозначение, пример.

Теорема.

. Теорема.

.

Теорема. Если два класса имеют общий элемент, то они совпадают.

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

Теорема. Наименьший неотрицательный вычет класса

равен остатку от деления

на

.

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

на

равен

, то абсолютно наименьший вычет класса

равен:

1)

; 2)

(если

- четное); 3)

.

Теорема. Класс вычетов числа

по модулю

является объединением

классов вычетов по модулю

. Пример.

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

Примеры (

. Таблицы сложения и умножения.

Теорема. Множество

классов вычетов по модулю

образует коммутативное кольцо.

Понятие делителя нуля в кольце. Примеры в кольце

.

Теорема. Поле не имеет делителей нуля.

Теорема. Если

- составное число, то

- не поле. Если

- простое число, то

- поле.

Примеры: 1) минимальное поле

; 2) обратные элементы в

.

Лекция 8

Полная система вычетов (ПСВ) по модулю .

Теорема. Любые

чисел, попарно не сравнимые между собой, образуют ПСВ.

Теорема. Пусть

- взаимно простые числа и

- любое число. Если

пробегает ПСВ, то

тоже пробегает ПСВ.

Теорема. Пусть

- взаимно простые числа,

пробегает ПСВ по модулю

- любое число. Тогда

пробегает ПСВ по модулю

Теорема. Все числа одного класса вычетов имеют одинаковый НОД с модулем.

Определение: НОД класса вычетов и модуля. Класс, взаимно простой с модулем. Приведенная система вычетов (ПрСВ).

Количество классов вычетов, взаимно простых с

, равно

.

Теорема. Любые

чисел, попарно не сравнимых между собой и взаимно простых с

, образуют ПрСВ по модулю

.

Теорема. Пусть

- взаимно простые числа. Если

пробегает ПрСВ по модулю

., то

тоже пробегает ПрСВ по модулю

.

Теорема. Пусть

- взаимно простые числа,

пробегает ПрСВ по модулю

. Тогда

пробегает ПрСВ по модулю

.

Следствие. Функция Эйлера мультипликативна.

Теорема Эйлера. Если и - взаимно простые числа, то

. Пример:

.

Малая теорема Ферма. Пусть

- простое число и

не делит

.

Тогда

.

Следствие.

для любого

Сравнения с неизвестной величиной.

Теорема. Пусть

- многочлен с целыми коэффициентами. Если

удовлетворяет сравнению

, то все числа класса вычетов

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

Определение решения сравнения. Способ перебора.

Пример:

.

Эквивалентные сравнения.

Преобразования сравнений:

1) замена коэффициентов;

2) прибавление (вычитание);

3) умножение (деление) обеих частей на число, взаимно простое с модулем;

4) умножение (деление) обеих частей и модуля на натуральное число.

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

Теорема. Если

не делит

, то сравнение не имеет решений.

Теорема. Если

, то существует единственное решение.

Теорема. Если

делит

, то существуют

решений, которые образуют класс вычетов по модулю

.

Лекция 9

Решение Сравнений 1-й степени.

Пример:

.

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

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

Теорема. Пусть

.

Тогда 1) если

не делит

, то решений нет,

2) если

делит

, то существует бесконечное множество

решений.

Теорема. Пусть

-частное решение неопределенного уравнения

. Пусть

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

Теорема. Пусть

-решение сравнения

. Тогда

- частное решение неопределенного уравнения

Системы сравнений. Пусть - многочлены с целыми коэффициентами. Рассмотрим систему сравнений (1) (1) и пусть

Если

удовлетворяет системе, то и весь класс

удовлетворяет системе.

Определение решения системы сравнений: класс вычетов

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

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

Китайская теорема об остатках. Пусть

попарно взаимно простые числа и

. Пусть

-решение сравнения

Тогда

- решение системы сравнений

Пример:

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

Лекция 10

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

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

Теорема. Сравнение

-й степени при

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

.

Теорема. Сравнение

-й степени имеет не более чем

решений.

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

Теорема. Пусть

. Тогда сравнение

(1) равносильно системе сравнений

(2)

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

решений. Тогда сравнение (1) имеет

решений.

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

Теорема.

.

Теорема.

. Следствие.

.

Теорема.

.

Пример: последние цифры

: 7,9,3,1.

Теорема.

.

Следствие 1.

.

Следствие 2. Пусть

. Количество степеней класса

, имеющих такой же показатель

, равно

Лекция 11

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

Пример (

.

Контрпример (

, первообразных корней не существует).

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

.

Теорема. Первообразные корни по модулю

существуют только для

(

-нечетное простое,

>0).

Индексы. Определение и пример индексов.

Контрпример (

).

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

.

Теорема. Пусть

- первообразный корень по модулю

. Тогда для любого числа

, взаимно простого с

, существует такое целое неотрицательное число

, что

. Множество таких

совпадает с неотрицательными числами некоторого класса вычетов по модулю

Теорема. Пусть

- первообразный корень по модулю

- взаимно просты с

. Тогда

.

Теорема. Пусть

- первообразный корень по модулю

- взаимно просты с

. Тогда

.

Следствие 1.

.

Следствие 2.

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

Теорема. Пусть

. Тогда: 1) если

не делит

, то сравнение не имеет решений; 2) если

делит

, то существуют

решений.

Определение. Вычет

-ой степени по модулю

.

Теорема. Вычеты

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

.

Замечание. Сравнения

имеют разные решения.

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

-ой степени равно

. Пример.

Лекция 12

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

степени

.

Определение. Корень

-ой степени из

.

Теорема. Все корни

-ой степени из

получаются из одного

умножением на все корни

-ой степени из

Показательные сравнения. . Пример: .
Сравнения 2-ой степени по простому модулю ( .

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

.

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

Пример:

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

Критерий Эйлера.

- квадратичный вычет, если

и квадратичный невычет, если

.

Пример:

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

. Квадратичными вычетами являются классы чисел

.

Пример:

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

Определение: Пусть

- простое число и

не кратно

.

Символ Лежандра числа

равен +1, если

- квадратичный

вычет по модулю

, и равен -1, если

- квадратичный невычет.

Обозначения:

Примеры: .

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

1)

;

2)

;

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

;

4)

;

5)

;

6)

, где

- количество чисел среди

, имеющих отрицательный абсолютно наименьший вычет;

7)

Пример: может ли

делиться на 29?

Лекция 13

Закон взаимности. Лемма. Пусть и - нечетные простые числа. Тогда .

.

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

.

Следствие. если хотя бы одно из чисел

сравнимо с 1 по модулю 4, то

, а если оба сравнимы с 3 по модулю 4, то

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

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

1)

;

2)

;

3)

;

Лемма. Если

-нечетные, то

.

Следствие.

.

4)

;

5)

;

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

Если

- нечетные взаимно простые, то

Приложение: Простые делители квадратичных форм. Пусть и слагаемые взаимно простые. Нечетное простое число .
Примеры:1);

;

3)

ЛИТЕРАТУРА

Основная:

И.М. Виноградов. Основы теории чисел. – М. Наука, 1981.
А.А. Бухштаб. Теория чисел. – М. Просвещение, 1968.
А.К. Сушкевич. Теория чисел. – Харьков, 1956.

Дополнительная:

Задачи и упражнения по теории чисел. Методическая разработка. Ч.1,2. Составители: Е.И. Гордон, С.А. Тюрин. –

г. Горький, ГГУ, 1986.

СОДЕРЖАНИЕ

Лекция 1	3
Лекция 2	3
Лекция 3	4
Лекция 4	5
Лекция 5	6
Лекция 6	7
Лекция 7	7
Лекция 8	8
Лекция 9	10
Лекция 10	11
Лекция 11	12
Лекция 12	13
Лекция 13	15
Литература.	17

Конспект лекций по курсу

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

Методическая разработка

Составитель

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

Подписано к печати . Формат 60х84 1/16.

Печать офсетная. Бумага офсетная. Усл. печ. л.

Тираж экз. Заказ № .

Нижегородский государственный университет им. Н.И. Лобачевского

603950, Н. Новгород, проспект Гагарина, 23.

Добавить документ в свой блог или на сайт

Конспект лекций по курсу «теория чисел»

Управление

филиалов

университета

ЛИТЕРАТУРА

СОДЕРЖАНИЕ

Лекция 1

Лекция 2

Лекция 3

Лекция 4

Лекция 5

Лекция 6

Лекция 7

Лекция 8

Лекция 9

Лекция 10

Лекция 11

Лекция 12

Лекция 13

Литература.

Похожие: