Теория чисел: конспект лекций ННГУ

Министерство образования и науки Российской Федерации
Нижегородский государственный университет
им. Н.И. Лобачевского
Управление
филиалов
университета
Выпуск №1
КОНСПЕКТ ЛЕКЦИЙ ПО КУРСУ
«ТЕОРИЯ ЧИСЕЛ»
Методическая разработка
Нижний Новгород
2010
УДК 511.17 Конспект лекций по курсу «Теория чисел». Методическая
разработка / Составитель Тюрин С.А. - Н.Новгород: ННГУ, 2010. – 19 с.
Рассмотрены следующие разделы теории чисел: теория делимости,
простые и составные числа, НОД и НОК, числовые функции, цепные дроби, теория сравнений, кольцо классов вычетов, решение сравнений, первообразные корни и индексы, сравнения 2-й степени, символ Лежандра, закон взаимности.
Для студентов механико-математического факультета.
Составитель:
Тюрин С.А.
Рецензент:
доцент кафедры
геометрии и высшей алгебры ННГУ
Разуваев А.Г.
 Нижегородский государственный
университет им. Н.И. Лобачевского,
2010 г.
2
Лекция 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
4. Простое число. Составное число.
Теорема. Наименьший положительный делитель не равный 1 – простое
число.
Теорема. Любое натуральное число большее 1 является либо простым, либо произведением простых.
Основная теорема арифметики. Любое натуральное число большее 1 раскладывается на простые множители единственным образом.
5. Каноническое разложение натурального (целого) числа.
Теорема. p-простое, p|abp|a или p|b.
Теорема о разложении на простые множители делителя натурального.
числа.
6. Теорема Евклида. Множество простых чисел бесконечно.
Лекция 2
Решето Эратосфена.
Теорема. Если натуральное число n>1 не делится ни на одно простое, не
превосходящее n , то оно простое.
Теорема. Если в множестве [2,N] вычеркнуть все числа, кратные первым r
простым числам, то первое незачеркнутое число – простое. Алгоритм
нахождения простых чисел.
1. Общее кратное. Примеры. НОК. Теорема. Любое общее кратное делится на наименьшее общее кратное. Обозначение НОК: [a1,a2,…,an]
2. Общий делитель. Единица является ОД. Множество ОД – конечно.
Определение: НОД – это такой ОД, который делится на все ОД. Обозначение НОД: (a1,a2,…,an).
Теорема. Для любых натуральных чисел a1,a2,…,an существует НОД.
(Для доказательства надо взять НОК всех ОД)
3. Взаимно простые числа.
3
Теорема:
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.
4. Теорема. Пусть m=[a,b], d=(a,b). Тогда md=ab.
Замечание. Для трех чисел это неверно.
Следствие. a и b взаимно просты  [a,b]=ab.
5. Нахождение НОД и НОК нескольких натуральных чисел.
Лемма. a=bлюбой делитель одного числа является делителем
второго и наоборот.
Теорема. (a1,a2,...,an)=((a1,a2,...,an-1),an).
Аналогичная теорема справедлива и для НОК.
6. Свойства взаимно простых чисел.
1) Если a и c – взаимно простые числа и c|ab, то c|b.
2) Если a и c – взаимно простые числа, то (ab,c)=(b,c).
3) Если a и c – взаимно простые числа и b и c – взаимно простые числа, то ab и c – взаимно простые числа.
7. Нахождение НОК и НОД разложением на простые множители.
8. Алгоритм Евклида.
Лекция 3
1. Свойство НОД. Теорема. a,b u,vZ такие, что au+bv=d – НОД
2. Следствие. (a,b)=1u,vZ такие, что au+bv=1.
Целая часть действительного числа.
3. Определение [x]. Наибольшее целое число, не превосходящее x.
n≤x<n+1, {x}=x-[x]
4. Теорема. Пусть x>0, xR, dN. Количество натуральных чисел, кратных d и не превосходящих x, равно [x/d].
5. Теорема. [x/d]=[[x]/d]. Следствие. [x/mn]=[[x/m]/n].
6. Теорема. Пусть nN и p- простое число. Тогда показатель кратности, с
которым число p входит в разложение n!, равно [n/p]+[n/p2]+[n/p3]+... .
Пример: p=5, n=50, k=12.
7. Числовые функции. Количество делителей (n), (20)=6.
Теорема. Если n=p1k1p2k2...psks, то (n)=(k1+1)(k2+1)...(ks+1).
 (n)   d , (20)=42.
d |n
p sk 1  1
p1k 1  1 p 2k 1  1

 ... 
Теорема.  ( n) 
.
p1  1 p 2  1
ps  1
1
s
2
4
Совершенные числа. Примеры: 6,28. Проблема существования нечетных
k 1
k
совершенных чисел. Вид четных совершенных чисел: p  2  (2  1) ,
если в скобке стоит простое число.
Функция Эйлера (n). Вид (p), (pn).
8. Мультипликативные и вполне мультипликативные функции.
Примеры: 1) (n), (n) 2) n 3) (n)- без доказательства.
Числовой интеграл. F (n)   f (d ) .
d |n
Теорема. Если f – мультипликативна, то и F – мультипликативна, причем
F (n)   [1  f ( p)  f ( p 2 )  ...  f ( p k )].
p|n
Примеры числовых интегралов: 1) 1 2) n 3)
Формула Гаусса   (d )  n .
d |n
Лекция 4
1. Цепные дроби. Определение. Запись   q0 , q1 ,..., qn  . Длина цепной дроби.
Цепная дробь – рациональное число. Пример: <2,7,3>=47/22.
Теорема. Любое рациональное число может быть представлено
конечной цепной дробью. Пример: 73/34=<2,6,1,4>.
Теорема. Разложение рационального числа в цепную дробь
единственно.
2. Подходящие дроби  k  q0 , q1 ,..., qk  для цепной дроби
  q0 , q1 ,..., qn  (k  n) .
Рекуррентные последовательности
P0  q0 , P1  q0 q1  1, Pk  Pk 1qk  Pk 2
Теорема.
Pk
 k .
Qk
Q0  1, Q1  q1 , Qk  Qk 1qk  Qk 2.
Таблицы для вычисления подходящих дробей.
3. Свойства подходящих дробей
k 1
1) Pk Qk 1  Pk 1Qk  (1) ;
2) Несократимость подходящих дробей;
Pk Pk 1 (1) k 1
3)


,
Qk Qk 1 Qk Qk 1
Pk Pk 1 (1) k 1
1
;



Qk Qk 1 Qk Qk 1 Qk Qk 1
4) Знаменатели подходящих дробей возрастают: Qk  Qk 1  Qk 2 ;
k
5) Pk Qk 2  Pk 2Qk  (1) qk ;
6) Дроби с четными номерами возрастают, с нечетными убывают;
7) Из двух соседних дробей дробь с четным номером меньше;
5
8) Любая дробь с четным номером меньше любой дроби с нечетным
номером;
9) Расстояния между соседними подходящими дробями уменьшаются.
4. Бесконечные цепные дроби   q0 , q1 ,..., qn ,... 
Теорема Существует предел последовательности подходящих дробей.
n .
Определение БЦД (бесконечной цепной дроби):   lim
n 
5. Полное и неполное частные БЦД:   q0 , q1 ,...,  n  .
P   Pn2
P  Qn2
,  n  n2
Теорема   n1 n
.
Qn1  n  Qn2
Qn1  Pn1
Теорема  n  qn , qn1 ,...  и qn   n .
Лекция 5
1. Теорема. Любое иррациональное действительное число может быть
разложено в БЦД.
Теорема. Разложение иррационального числа в БЦД единственно.
2. Квадратичная иррациональность. Пример и контрпример.
3. Периодическая БЦД.
Определение. s  0, k  0n  s  qn  qn k
Критерий периодичности: s  0, k  0 :  s   s  k
Теорема. Любая периодическая БЦД есть квадратичная иррациональность.  s 
Ps 2  Qs 2
Qs 1  Ps 1
Нахождение квадратного уравнения для периодической БЦД.
4. Лемма о дискриминанте. Пусть  -квадратичная иррациональность с
2
дискриминантом D  B  AC . Тогда любое полное частное  n является квадратичной иррациональностью с тем же дискриминантом.
5. Теорема Лагранжа. Любая квадратичная иррациональность разлагается в периодическую БЦД.
Пример: 8  2, (1,4) 
6. Приближение иррациональных чисел подходящими дробями.
  n 
1
1
1
,   n  2 ,   n 
,
Qn Qn1
Qn
Qn (Qn  Qn1 )
1
1
   n 
2Qn Qn1
Qn Qn1
6
Лекция 6
1. Наилучшие приближения действительных чисел.
a
- наилучшее приближение к  , если
b
x
a
      y b
y
b
a c 
Теорема. Пусть    ,  и bc  ad  1 . Тогда ближайший из
b d 
концов интервала является наилучшим приближением к  .
Определение:
Теорема. Любая подходящая дробь является наилучшим приближением к  .
2. Применения цепных дробей: 1) Зубчатые колеса; 2) Календарный
стиль: юлианский и грегорианский календарь.
3. Сравнения. Определение и примеры.
Теорема. a  b mod m  a и b имеют одинаковые остатки при делении на m .
4. Свойства сравнений:
1) рефлексивность;
2) симметричность;
3) транзитивность;
4) a  b(m)  ka  kb(m) ;
5) ka  kb(m) и (k , m)  1  a  b(m) ;
6) a  b(m), k  0  ka  kb(km) ;
7) ka  kb(km)  a  b(m) ;
8) Сложение и вычитание сравнений;
9) Умножение сравнений;
10) Возведение в степень;
11) Если f ( x)  Z [ x], a  b(m)  f (a)  f (b)(m) ;
12) Перенос слагаемых с изменением знака;
13) a  b(m), d m  a  b(d ) ;
14) a  b(m)  множество общих делителей a и m совпадает с
множеством общих делителей b и m ;
15) a  b(m1 ),..., a  b(mn )  a  b( M ) , где M - НОК (a, b) .
Лекция 7
7. Классы вычетов. Определение, обозначение, пример.
7
Теорема. a  {a  mt t  Z } . Теорема. a  b  a  b(m) .
Теорема. Если два класса имеют общий элемент, то они совпадают.
8. Определение: вычет класса.
Теорема. Наименьший неотрицательный вычет класса a равен
остатку от деления a на m .
Теорема. Если остаток от деления a на m равен r , то абсолютно
наименьший вычет класса a равен:
m
m
m
; 2)  r , r 
(если m - четное); 3) r  m,  r  m .
2
2
2
Теорема. Класс вычетов числа a по модулю m является объединением d классов вычетов по модулю dm . Пример.
1) r ,0  r 
9. Кольцо классов вычетов. Определение кольца. Операции сложения и
умножения классов вычетов. Корректность.
Примеры ( m  5,6) . Таблицы сложения и умножения.
Теорема. Множество Z m классов вычетов по модулю m образует
коммутативное кольцо.
Понятие делителя нуля в кольце. Примеры в кольце Z 6 .
Теорема. Поле не имеет делителей нуля.
Теорема. Если m - составное число, то Z m - не поле. Если m - простое число, то Z m - поле.
Примеры: 1) минимальное поле Z 2 ; 2) обратные элементы в Z 5 .
Лекция 8
1. Полная система вычетов (ПСВ) по модулю m .
Теорема. Любые m чисел, попарно не сравнимые между собой, образуют ПСВ.
Теорема. Пусть a и m - взаимно простые числа и b - любое число.
Если x пробегает ПСВ, то ax  b тоже пробегает ПСВ.
Теорема. Пусть a и b - взаимно простые числа, x пробегает ПСВ по
модулю b , y пробегает ПСВ по модулю a , c - любое число. Тогда
ax  by  c пробегает ПСВ по модулю a  b .
2. Теорема. Все числа одного класса вычетов имеют одинаковый НОД
с модулем.
Определение: НОД класса вычетов и модуля. Класс, взаимно простой с модулем. Приведенная система вычетов (ПрСВ).
Количество классов вычетов, взаимно простых с m , равно  (m) .
8
Теорема. Любые  (m) чисел, попарно не сравнимых между собой и
взаимно простых с m , образуют ПрСВ по модулю m .
Теорема. Пусть a и m - взаимно простые числа. Если x пробегает
ПрСВ по модулю m ., то ax тоже пробегает ПрСВ по модулю m .
Теорема. Пусть a и b - взаимно простые числа, x пробегает ПрСВ
по модулю b , y пробегает ПрСВ по модулю a . Тогда ax  by
пробегает ПрСВ по модулю ab .
Следствие. Функция Эйлера мультипликативна.
3. Теорема Эйлера. Если a и m - взаимно простые числа, то
a ( m )  1(mod m) . Пример: m  10,  (m)  4, a  3 .
Малая теорема Ферма. Пусть p - простое число и p не делит a .
p 1
Тогда a  1(mod p) .
p
Следствие. a  a(mod p) для любого a  Z .
4. Сравнения с неизвестной величиной.
Теорема. Пусть f ( x)  Z [ x] - многочлен с целыми коэффициентами. Если a  Z удовлетворяет сравнению f ( x)  0(mod m) , то все
числа класса вычетов a удовлетворяют этому сравнению.
Определение решения сравнения. Способ перебора.
3
Пример: x  x  2  0(mod 7), x  1(mod 7), x  3(mod 7) .
Эквивалентные сравнения.
Преобразования сравнений:
1) замена коэффициентов;
2) прибавление (вычитание);
3) умножение (деление) обеих частей на число, взаимно простое с
модулем;
4) умножение (деление) обеих частей и модуля на натуральное число.
5. Сравнения 1-ой степени. ax  b(mod m)
Теорема. Если (a, m)  d и d не делит b , то сравнение не имеет
решений.
Теорема. Если (a, m)  1, то существует единственное решение.
Теорема. Если (a, m)  d и d делит b , то существуют d решений,
которые образуют класс вычетов по модулю
9
m
.
d
Лекция 9
10.Решение Сравнений 1-й степени. ax  b(mod m)
Пример: 3x  5(mod 7) , x  5  3  4(mod 7) .
5
m
 q0 , q1 ,..., qn  ,
a
Pn1Qn  Pn Qn1  (1) n , m  Pn , a  Qn , x  (1) n b  Pn1 (mod m)
11.Неопределенные уравнения. a1 x1  a2 x2  ...  an xn  b .
Теорема. Пусть НОД (a1 , a2 ,..., an )  d .
Тогда 1) если d не делит b , то решений нет,
2) если d делит b , то существует бесконечное множество
С помощью цепных дробей: (a, m)  1,
решений.
Теорема. Пусть ( x0 , y0 ) -частное решение неопределенного уравнения ax  by  c . Пусть d  НОД (a, b) и d c . Тогда общее решение
имеет следующий вид:
b

x

x

t,
0

d
t Z

a
 y  y0  t.

d
Теорема. Пусть
x0 -решение сравнения ax  c(mod b) . Тогда
c  ax0
) - частное решение неопределенного уравнения
b
ax  by  c .
12.Системы сравнений. Пусть f1 , f 2 ,..., f n  Z [ x] - многочлены с це( x0 ,
лыми
коэффициентами.
Рассмотрим
систему
сравнений
 f1 ( x)  0(mod m1 )

............................... (1) и пусть M  НОК (m1 , m2 ,..., mn )
 f ( x)  0(mod m )
n
 n
(1)
Если a  Z удовлетворяет системе, то и весь класс a (mod M ) удовлетворяет системе.
Определение решения системы сравнений: класс вычетов (mod M )
10
 x  c1 (mod m1 )
,

x

c
(mod
m
)

2
2
d  (m1 , m2 ), M  [m1 , m2 ] . Если d не делит c2  c1 , то система не
имеет решений, если d c2  c1 , то существует одно решение.
13.Теорема.
Рассмотрим
систему
Обобщение: в случае системы из нескольких сравнений такого вида
существует одно решение или система не имеет решений.
Китайская теорема об остатках. Пусть m1 ,..., mn попарно взаимно
простые числа и M  m1  ...  mn . Пусть xi -решение сравнения
M
M
M
x  1(mod mi ), i  1,..., n. Тогда x0 
x1c1  ... 
xn cn - реmi
m1
mn
 x  c1 (mod m1 )

шение системы сравнений ...............................
 x  c (mod m )
n
n

Пример:
 x  2(3)

 x  3(5) , M  105, x1  2, x2  1, x3  1, x0  233  23(105) .
 x  2(7)

14.Теорема Вильсона. Если p - простое число, то ( p  1)! 1(mod p) .
Лекция 10
1. Сравнения высшей степени по простому модулю.
Теорема. Сравнение высшей степени равносильно сравнению со
старшим коэффициентом, равным 1.
Теорема. Сравнение n -й степени при n  p равносильно сравнению
степени меньшей, чем p .
Теорема. Сравнение n -й степени имеет не более чем n решений.
2. Сравнения по составному модулю.
k
k
k
Теорема. Пусть m  p1  p2  ...  ps . Тогда сравнение
f ( x)  0(mod m) (1) равносильно системе сравнений
1
2
s
 f ( x)  0(mod p1 )

............................... (2)
 f ( x)  0(mod p k )
s

k1
s
11
Теорема. Пусть сравнения системы (2) имеют соответственно
l1 , l2 ,..., ls решений. Тогда сравнение (1) имеет l  l1  ...  ls решений.
3. Сравнения вида
f ( x)  0(mod p k ) . Вспомогательное сравнение
f ( x)  0(mod p) . Строится последовательность приближений
i
ai  ai 1 (mod p )
a0 , a1 ,..., ak 1 , так что выполняются условия 
i 1
 f (ai )  0 mod( p )
для всех i  1,2,..., k  1. При этом должно выполняться условие p
2
i
не делит f (a0 ) .Получим ai  a0  c1 p  c2 p  ...  ci p .
4. Показатель класса. Определение Pm (a ) . Пример: P11 (3)  5 .
Теорема. a  b(mod m)  Pm (a)  Pm (b) .
n
Теорема. a  1(mod m)  Pm (a ) n . Следствие. Pm (a )  (m) .
s
t
Теорема. a  a (mod m)  s  t (mod Pm (a)) .
k
Пример: последние цифры 7 : 7,9,3,1.
Pm (a )
k
Теорема. Pm ( a ) 
.
( Pm (a ), k )
k
Следствие 1. Pm (a )  Pm (a)  ( Pm (a), k )  1 .
Следствие 2. Пусть Pm (a)  n . Количество степеней класса a , имеющих такой же показатель n , равно  (n).
Лекция 11
1. Теорема. 1) Если Pm (a)  n , классы a, a ,..., a являются некоторы2
n
ми решениями сравнения x  1(mod m) ; 2) Если m - простое число, то эти классы дают все решения этого сравнения.
2. Первообразные корни. Определение: Pm (a )   (m) .
Пример ( m  7, a  3) .
Контрпример ( m  8 , первообразных корней не существует).
Теорема. Если модуль – простое число, то первообразный корень
существует. В этом случае количество первообразных корней равно
 ( p  1) .
Теорема. Первообразные корни по модулю m существуют только
k
k
для m  2,4, p ,2 p ( p -нечетное простое, k >0).
3. Индексы. Определение и пример индексов.
Контрпример ( m  10, a  9, b  3 ).
n
12
Таблица индексов ( m  11, g  2) .
Теорема. Пусть g - первообразный корень по модулю m . Тогда для
любого числа b , взаимно простого с m , существует такое целое неs
отрицательное число s , что g  b(mod m) . Множество таких s
совпадает с неотрицательными числами некоторого класса вычетов
по модулю  (m).
Теорема. Пусть g - первообразный корень по модулю m , b и c взаимно просты с m . Тогда
b  c(mod m)  ind g b  ind g c(mod  (m)) .
Теорема. Пусть g - первообразный корень по модулю m , b и c взаимно просты с m . Тогда
ind g (bc)  ind g b  ind g c(mod  (m)) .
n
Следствие 1. ind g (b1b2 ...bn )   ind g bi (mod  (m)) .
i 1
Следствие 2. ind g (b )  n  ind g b(mod  (m)) .
n
4. Двучленные сравнения по простому модулю. Ax  B(mod p) .
n
Приводятся к виду x  a(mod p) , где p не делит a .
Теорема. Пусть d  (n, p  1) . Тогда: 1) если d не делит ind (a) , то
сравнение не имеет решений; 2) если d делит ind (a) , то существуют d решений.
Определение. Вычет n -ой степени по модулю p .
Теорема. Вычеты n -ой степени совпадают с вычетами степени
d  (n, p  1) .
n
d
Замечание. Сравнения x  a(mod p) и x  a(mod p) имеют разные решения.
n
Теорема. Число классов вычетов n -ой степени равно
n  9, d  3, g  2, y  3,6,9,12  x  8,12,5,1.
p 1
. Пример.
d
Лекция 12
1. Теорема. Пусть n ( p  1) . Тогда a является вычетом n -ой
степени  a
p 1
n
 1( p) .
Определение. Корень n -ой степени из a .
Теорема. Все корни n -ой степени из a получаются из одного
13
умножением на все корни n -ой степени из 1.
x
x
2. Показательные сравнения. a  b(mod m) . Пример: 4  9(13) .
x1  4(12), x2  10(12).
3. Сравнения
2-ой
простому модулю
Ax 2  Bx  C  0( p)  x 2  a( p) .
Число решений равно 0 или 2: x  x0 ( p ), x   x0 ( p ) .
Определение: квадратичный вычет и невычет.
2
Пример: x  2(5) не имеет решений.
Критерий Эйлера.
степени
по
a - квадратичный вычет, если a
p 1
2
( p  2).
 1( p) и
p 1
2
квадратичный невычет, если a  1( p ) .
6
6
Пример: p  13,2  1(13),3  1(13).
Теорема. Число классов квадратичных вычетов равно числу клас-
p 1
. Квадратичными вы2
2
 p 1
2
2
четами являются классы чисел 1 ,2 ,...,
 .
2


2
2
2
2
2
Пример: p  11, 1 ,2 ,3 ,4 ,5   1,3,4,5,9.
сов квадратичных невычетов и равно
4. Символ Лежандра.
Определение: Пусть p - простое число и a не кратно p .
Символ Лежандра числа a равен +1, если a - квадратичный
вычет по модулю p , и равен -1, если a - квадратичный невычет.
a
  L(a, p) .
 p
3
7
5. Примеры:    1,    1 .
 11 
 11 
Обозначения: 
Свойства символа Лежандра:
a b
    ;
p
   p
1) a  b( p)  
 a2 
2)    1;
 p
p1
a
3) Критерий Эйлера:    a 2 ( p) ;
 p
14
  1   1, p  1(4)
;
  

1
,
p

3
(
4
)
p
  
 a a ...a   a  a 
a 
5)  1 2 n    1  2   ...   n  ;
p   p  p 

 p
a
 p 1
l
6)    (1) , где l - количество чисел среди a,2a,..., 
a ,
2
p


 
4) 
имеющих отрицательный абсолютно наименьший вычет;
p 1
 2   1, p  1(8) или p  7(8)
7)    
 (1) 8
 p   1, p  3(8) или p  5(8)
2
Пример: может ли n  2 делиться на 29?
2
Лекция 13
1. Закон взаимности. Лемма. Пусть p и q - нечетные простые чисp 1
2
q 1
 qx  2  py  p  1 q  1
ла. Тогда        
.

x 1
2
2
 p  y 1  q 
( x, y )  qx  py .
p 1 q 1

 p  q 
Теорема (Закон взаимности).
    (1) 2 2 .
 q  p 
Следствие. если хотя бы одно из чисел p и q сравнимо с 1 по
 p  q 
модулю 4, то      , а если оба сравнимы с 3 по модулю 4,
 q   p
 p
q
то      .
q
 p
2. Символ Якоби. m  p1 p2 ... ps -нечетное, p1 , p2 ,... ps -простые (м.б.
a
a
одинаковые), (a, m)  1. Символ Якоби равен       .
m p m p
Свойства символа Якоби.
a b
   ;
m
  m
1) a  b( m)  
a 
2)    1;
m
2
15
 a1a2 ...an   a1  a2 
a 
      ...   n  ;
 m   m  m 
m
mk  1 m  1 k  1
Лемма. Если m, k -нечетные, то


(mod 2) ,
2
2
2
2
2
2
(mk )  1 m  1 k  1


(mod 2) .
8
8
8
m2  1
p2 1
m 1
p 1

(mod 2) .

(mod 2) ,
Следствие.
8
8
2
pm
pm 2
m 1
 1
2

(

1
)
4) 
;

m
m 1
2
8

(

1
)
5)  
;
m
3) 
2
6) Закон взаимности.
m 1 k 1

 m  k 
Если m, k - нечетные взаимно простые, то     ( 1) 2 2 .
 k  m 
3. Приложение: Простые делители квадратичных форм. Пусть
N  ax 2  by 2 и слагаемые взаимно простые. Нечетное простое
p 1
 ab 
  (1) 2 .
 p
2
2
4. Примеры:1) N  x  y  p  4n  1;
2
2
2) N  x  2 y  p  8n  1, p  8n  3 ;
2
2
3) N  x  2 y  p  8n  1, p  8n  7 .
число p N  
16
ЛИТЕРАТУРА
Основная:
1. И.М. Виноградов. Основы теории чисел. – М. Наука, 1981.
2. А.А. Бухштаб. Теория чисел. – М. Просвещение, 1968.
3. А.К. Сушкевич. Теория чисел. – Харьков, 1956.
Дополнительная:
1. Задачи и упражнения по теории чисел. Методическая разработка. Ч.1,2. Составители: Е.И. Гордон, С.А. Тюрин. –
г. Горький, ГГУ, 1986.
17
СОДЕРЖАНИЕ
Лекция 1
Лекция 2
Лекция 3
Лекция 4
Лекция 5
Лекция 6
Лекция 7
Лекция 8
Лекция 9
Лекция 10
Лекция 11
Лекция 12
Лекция 13
Литература.
3
3
4
5
6
7
7
8
10
11
12
13
15
17
18
Конспект лекций по курсу
«Теории чисел»
Методическая разработка
Составитель
Тюрин Сергей Андреевич
Подписано к печати
. Формат 60х84 1/16.
Печать офсетная. Бумага офсетная. Усл. печ. л.
Тираж
экз. Заказ №
.
Нижегородский государственный университет им. Н.И. Лобачевского
603950, Н. Новгород, проспект Гагарина, 23.
19