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


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



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

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

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






Управление

филиалов

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







Выпуск №1







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

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


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


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


2010


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


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

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


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


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

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

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


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

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

2010 г.

Лекция 1


  1. Теорема о делении с остатком. а>0, a=0, a<0. Единственность. Делимое, делитель, частное, остаток.

  2. Делитель, кратное. Теорема: b>0 – делитель т. и т.т. когда остаток равен нулю. Обозначение: b|a.

  3. Свойства делимости. 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|a1, c|a2, ..., c|an c|a1b1+a2b2+...+anbn

10) b1|a1, b2|a2, ..., bn|anb1b2...bn|a1a2...an 11) b|abn|an

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

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

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

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

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

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

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

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



Лекция 2


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

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

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

  1. Общее кратное. Примеры. НОК. Теорема. Любое общее кратное делится на наименьшее общее кратное. Обозначение НОК: [a1,a2,…,an]

  2. Общий делитель. Единица является ОД. Множество ОД – конечно. Определение: НОД – это такой ОД, который делится на все ОД. Обозначение НОД: (a1,a2,…,an).

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

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

Теорема: d=(a1,a2,...,an)d является ОД и числа {a1/d, a2/d, ...an/d} –

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

Теорема. 1) Если (a1,a2,...,an)=d, то (ka1,ka2,...,kan)=kd;

2) Если k=ОД, то (a1/k, a2/k,...,an/k)=d/k.

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

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

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

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

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

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

Теорема. (a1,a2,...,an)=((a1,a2,...,an-1),an).

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

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

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

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

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

  1. Нахождение НОК и НОД разложением на простые множители.

  2. Алгоритм Евклида.



Лекция 3


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

  2. Следствие. (a,b)=1u,vZ такие, что au+bv=1.

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

  1. Определение [x]. Наибольшее целое число, не превосходящее x. n≤x

  2. Теорема. Пусть x>0, xR, dN. Количество натуральных чисел, кратных d и не превосходящих x, равно [x/d].

  3. Теорема. [x/d]=[[x]/d]. Следствие. [x/mn]=[[x/m]/n].

  4. Теорема. Пусть nN и p- простое число. Тогда показатель кратности, с которым число p входит в разложение n!, равно [n/p]+[n/p2]+[n/p3]+... . Пример: p=5, n=50, k=12.

  5. Числовые функции. Количество делителей (n), (20)=6.

Теорема. Если n=p1k1p2k2...psks, то (n)=(k1+1)(k2+1)...(ks+1).

, (20)=42.

Теорема. .

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

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

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

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

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

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

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

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

Лекция 4


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

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

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

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

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

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

  1. П
    Теорема. .

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

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



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

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

1) ;

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

3) ;

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

5) ;

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

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

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

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

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

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

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

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

Теорема .

Теорема и .


Лекция 5


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

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

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

  2. Периодическая БЦД.

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

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

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

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

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

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

Пример:

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




Лекция 6


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

Определение: - наилучшее приближение к , если

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

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

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

  2. Сравнения. Определение и примеры.

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

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

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

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

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

4) ;

5) и ;

6) ;

7) ;

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

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

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

11) Если ;

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

13) ;

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

15) , где - НОК.


Лекция 7


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

Теорема. . Теорема. .

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

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

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

Теорема. Если остаток от деления на равен , то абсолютно наименьший вычет класса равен:

1) ; 2) (если - четное); 3) .

Теорема. Класс вычетов числа по модулю является объединением классов вычетов по модулю . Пример.

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

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

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

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

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

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

Примеры: 1) минимальное поле ; 2) обратные элементы в .


Лекция 8


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

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

Теорема. Пусть и - взаимно простые числа и - любое число. Если пробегает ПСВ, то тоже пробегает ПСВ.

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

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

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

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

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

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

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

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

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

. Пример: .

Малая теорема Ферма. Пусть - простое число и не делит .

Тогда .

Следствие. для любого .

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

Теорема. Пусть - многочлен с целыми коэффициентами. Если удовлетворяет сравнению , то все числа класса вычетов удовлетворяют этому сравнению.

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

Пример: .

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

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

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

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

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

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

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

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

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

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


Лекция 9


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



Пример:, .

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

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

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

Тогда 1) если не делит , то решений нет,

2) если делит , то существует бесконечное множество

решений.

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



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

.

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

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

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


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

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

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

Пример: .

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


Лекция 10


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

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

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

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

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

Теорема. Пусть . Тогда сравнение

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

(2)


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

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

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

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

Теорема. .

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

Теорема. .

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

Теорема. .

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

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


Лекция 11


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

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

Пример (.

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

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

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

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

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

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

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

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

.

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

.

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

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

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

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

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

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

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

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


Лекция 12


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

степени.

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

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

умножением на все корни -ой степени из .

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

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

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

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

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

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

Пример:

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

Пример: .

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

Определение: Пусть - простое число и не кратно .

Символ Лежандра числа равен +1, если - квадратичный

вычет по модулю , и равен -1, если - квадратичный невычет.

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

  1. Примеры: .

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

1) ;

2) ;

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

4) ;

5) ;

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

7)

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


Лекция 13


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

.

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

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

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

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

1) ;

2) ;

3) ;

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

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

4) ;

5) ;

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

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

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

  2. Примеры:1);

2) ;

3) .


ЛИТЕРАТУРА



Основная:

      1. И.М. Виноградов. Основы теории чисел. – М. Наука, 1981.

      2. А.А. Бухштаб. Теория чисел. – М. Просвещение, 1968.

      3. А.К. Сушкевич. Теория чисел. – Харьков, 1956.


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

  1. Задачи и упражнения по теории чисел. Методическая разработка. Ч.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.


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

Похожие:

Разместите кнопку на своём сайте:
cat.convdocs.org


База данных защищена авторским правом ©cat.convdocs.org 2012
обратиться к администрации
cat.convdocs.org
Главная страница