Теория чисел:Тикеты — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Лекция - Основные элементы теории чисел)
м (rollbackEdits.php mass rollback)
 
(не показано 11 промежуточных версий 2 участников)
Строка 1: Строка 1:
 +
'''Почти для всех конспектов есть одна большая правка: сделать конспект нормальным'''
 
== 1 Классы чисел и основная теорема арифметики ==
 
== 1 Классы чисел и основная теорема арифметики ==
 
# [[Классы чисел]] 1-1,5
 
# [[Классы чисел]] 1-1,5
Строка 27: Строка 28:
 
# [[Теоремы о простых числах]] 2
 
# [[Теоремы о простых числах]] 2
 
## переместить в конспект с простыми числами и нормально оформить
 
## переместить в конспект с простыми числами и нормально оформить
−
=== Практика - Разложение на множители и длинная арифметика ===
+
<!--=== Практика - Разложение на множители и длинная арифметика ===-->
 
# [[Системы счисления]] 2
 
# [[Системы счисления]] 2
 
## Нормально заюзать тех
 
## Нормально заюзать тех
Строка 50: Строка 51:
 
## поправить статью
 
## поправить статью
  
−
== Лекция - Основные элементы теории чисел ==
+
== 2 Лекция - Основные элементы теории чисел ==
−
* [[Сравнения, система вычетов, решение линейных систем по модулю]] 5-10-15
+
# [[Сравнения, система вычетов, решение линейных систем по модулю]] 5-10-15
 
## поправить тех
 
## поправить тех
 
## источники информации, см также
 
## источники информации, см также
 
## сделать конспект нормальным
 
## сделать конспект нормальным
 
## разбить на 3 конспекта
 
## разбить на 3 конспекта
−
* [[Китайская теорема об остатках]] 1-5
+
# [[Китайская теорема об остатках]] 1-5
 
## поправить тех
 
## поправить тех
 
## источники информации, см также
 
## источники информации, см также
 
## добавить информации или поместить в конспект, где она должна быть теорема
 
## добавить информации или поместить в конспект, где она должна быть теорема
−
* [[Теорема Ферма]] 1-5
+
# [[Теорема Ферма]] 1-5
 
## все правки из китайской теоремы об остатках
 
## все правки из китайской теоремы об остатках
−
* [[Теорема Вильсона]] 1-5
+
# [[Теорема Вильсона]] 1-5
 
## все правки из китайской теоремы об остатках  
 
## все правки из китайской теоремы об остатках  
−
* [[Мультипликативность функции, свертка Дирихле]] 5-10
+
# [[Мультипликативность функции, свертка Дирихле]] 5-10
 
## разбить на 2, добавить информации
 
## разбить на 2, добавить информации
 
## поправить тех
 
## поправить тех
 
## английские термины
 
## английские термины
 
## добавить использование шаблонов теорем/утверждений
 
## добавить использование шаблонов теорем/утверждений
−
* [[Функция Эйлера]] 1
+
# [[Функция Эйлера]] 1
 
## поправить тех
 
## поправить тех
 
## английские термины
 
## английские термины
 
## добавить использование шаблонов терем/утверждений
 
## добавить использование шаблонов терем/утверждений
 
## придать структуру
 
## придать структуру
−
* [[Количество делителей, сумма делителей]]
+
# [[Количество делителей, сумма делителей]]
 +
# [[Функция Мебиуса]]
  
−
* [[Функция Мебиуса]]
+
<!--=== Практика - Основные алгоритмы теории чисел ===-->
 +
# [[Решето Эратосфена]]
 +
# [[Быстрое возведение в степень]]
 +
# [[Умножение по Монтгомери]]
 +
# [[Дискретное преобразование Фурье]]
 +
# [[Быстрое преобразование Фурье]]
  
−
=== Практика - Основные алгоритмы теории чисел ===
+
== 3 Лекция - Основы теории групп ==
−
* [[Решето Эратосфена]]
+
# [[Полугруппа]], [[моноид]], [[группа]]
−
* [[Быстрое возведение в степень]]
+
# [[Абелева группа]], [[Конечная группа]]
−
* [[Умножение по Монтгомери]]
+
# [[Гомоморфизм групп]], [[изоморфизм групп]]
−
* [[Дискретное преобразование Фурье]]
+
# [[Подгруппа]], [[нормальная подгруппа]]
−
* [[Быстрое преобразование Фурье]]
+
# [[Порядок элемента группы]], [[циклическая группа]], [[конечно порожденная группа]]
 +
# [[Регулярное представление группы]]
 +
# [[Теорема о подгруппах циклической группы]]
 +
# [[Смежные классы]], [[теорема Лагранжа]], [[факторгруппы]]
 +
<!--=== Практика - Основы теории групп ===-->
 +
# [[Вычисление порядка элемента в группе]]
 +
# [[Вычисление порядка перестановки в группе перестановок]]
 +
# [[Дискретное логарифмирование в группе]]
 +
# [[Действие группы на множестве]]
 +
# [[Лемма Бернсайда, задача о числе ожерелий]]
 +
# [[Представление групп]]
  
−
== Лекция - Основы теории групп ==
+
== 4 Лекция - Основы теории колец ==
−
* [[Полугруппа]], [[моноид]], [[группа]]
+
#[[Определение кольца, подкольца, изоморфизмы колец]]
−
* [[Абелева группа]], [[Конечная группа]]
+
#[[Делители нуля, области целостности]]
−
* [[Гомоморфизм групп]], [[изоморфизм групп]]
+
#[[Единицы (обратимые элементы), группа обратимых элементов]]
−
* [[Подгруппа]], [[нормальная подгруппа]]
+
#[[Неразложимые элементы, ассоциированные элементы и разложение на множители в целостных кольцах]]
−
* [[Порядок элемента группы]], [[циклическая группа]], [[конечно порожденная группа]]
+
#[[Евклидовы кольца]]
−
* [[Регулярное представление группы]]
+
<!--=== Практика - Арифметика полиномов от одной переменной над полем ===-->
−
* [[Теорема о подгруппах циклической группы]]
 
−
* [[Смежные классы]], [[теорема Лагранжа]], [[факторгруппы]]
 
−
=== Практика - Основы теории групп ===
 
−
* [[Вычисление порядка элемента в группе]]
 
−
* [[Вычисление порядка перестановки в группе перестановок]]
 
−
* [[Дискретное логарифмирование в группе]]
 
−
* [[Действие группы на множестве]]
 
−
* [[Лемма Бернсайда, задача о числе ожерелий]]
 
−
* [[Представление групп]]
 
  
−
== Лекция - Основы теории колец ==
+
== 5 Лекция - Основы теории полей ==
−
*[[Определение кольца, подкольца, изоморфизмы колец]]
+
# [[Определение поля и подполя, изоморфизмы полей]]
−
*[[Делители нуля, области целостности]]
+
# [[Примеры полей]]
−
*[[Единицы (обратимые элементы), группа обратимых элементов]]
+
# [[Мультипликативная группа поля]]
−
*[[Неразложимые элементы, ассоциированные элементы и разложение на множители в целостных кольцах]]
+
# [[Расширения полей]]
−
*[[Евклидовы кольца]]
 
−
=== Практика - Арифметика полиномов от одной переменной над полем ===
 
  
−
== Лекция - Основы теории полей ==
+
== 6 Лекция - Первообразные корни и квадратичные вычеты ==
−
* [[Определение поля и подполя, изоморфизмы полей]]
+
# [[Теорема о цикличности мультипликативной группы поля Z/pZ|Теорема о цикличности мультипликативной группы поля <tex>\mathbb{Z}/p\mathbb{Z}</tex>]]
−
* [[Примеры полей]]
+
# [[Первообразные корни]]
−
* [[Мультипликативная группа поля]]
+
# [[Существование первообразных корней по определенным модулям|Теорема о существовании первообразных корней по модулям вида <tex>2,4,p^n,2\cdot p^n</tex>]]
−
* [[Расширения полей]]
+
# [[Квадратичные вычеты|Квадратичные вычеты, количество квадратичных вычетов по простому модулю]]
 +
# [[Символ Лежандра, критерий Эйлера]]
 +
# [[Теорема о (((p-1)/2)!)^2=-1(mod p)|Теорема о <tex>((\frac{p-1}{2})!)^2\equiv -1 (mod ~p)</tex> при <tex>p=4\cdot k+1</tex>]]
 +
# [[Лемма Гаусса для вычисления квадратичного характера числа по простому модулю]]
 +
<!--=== Практика - Первообразные корни и квадратичные вычеты ===-->
  
−
== Лекция - Первообразные корни и квадратичные вычеты ==
+
== 7 Лекция - Квадратичные вычеты ==
−
* [[Теорема о цикличности мультипликативной группы поля Z/pZ|Теорема о цикличности мультипликативной группы поля <tex>\mathbb{Z}/p\mathbb{Z}</tex>]]
+
#[[Квадратичный закон взаимности]]
−
* [[Первообразные корни]]
+
#[[Символ Якоби и его свойства]]
−
** [[Существование первообразных корней по определенным модулям|Теорема о существовании первообразных корней по модулям вида <tex>2,4,p^n,2\cdot p^n</tex>]]
+
#[[Обобщенный квадратичный закон взаимности]]
−
* [[Квадратичные вычеты|Квадратичные вычеты, количество квадратичных вычетов по простому модулю]]
+
#[[Алгоритм вычисления символа Якоби]]
−
** [[Символ Лежандра, критерий Эйлера]]
+
<!--=== Практика - Вероятностные тесты чисел на простоту ===-->
−
** [[Теорема о (((p-1)/2)!)^2=-1(mod p)|Теорема о <tex>((\frac{p-1}{2})!)^2\equiv -1 (mod ~p)</tex> при <tex>p=4\cdot k+1</tex>]]
+
#[[Тест Ферма проверки чисел на простоту, числа Кармайкла]]
−
** [[Лемма Гаусса для вычисления квадратичного характера числа по простому модулю]]
+
#[[Тест Соловея-Штрассена]]
−
=== Практика - Первообразные корни и квадратичные вычеты ===
+
#[[Тест Миллера-Рабина]]
  
−
== Лекция - Квадратичные вычеты ==
+
== 8 Лекция - Аналитическая теория чисел ==
−
*[[Квадратичный закон взаимности]]
+
# [[Факты из математического анализа]]
−
*[[Символ Якоби и его свойства]]
+
# [[Теорема Чебышёва]]
−
*[[Обобщенный квадратичный закон взаимности]]
+
# [[Постулат Бертрана]]
−
*[[Алгоритм вычисления символа Якоби]]
+
# [[Уточнение констант в теореме Чебышёва]]
−
=== Практика - Вероятностные тесты чисел на простоту ===
+
# [[Сумма обратных к простым]]
−
*[[Тест Ферма проверки чисел на простоту, числа Кармайкла]]
+
# [[Асимптотический закон распределения простых чисел]]
−
*[[Тест Соловея-Штрассена]]
 
−
*[[Тест Миллера-Рабина]]
 
  
−
== Лекция - Аналитическая теория чисел ==
+
<!--=== Практика - Вычисление <math>\pi(x)</math> ===-->
−
* [[Факты из математического анализа]]
 
−
* [[Теорема Чебышёва]]
 
−
* [[Постулат Бертрана]]
 
−
* [[Уточнение констант в теореме Чебышёва]]
 
−
* [[Сумма обратных к простым]]
 
−
* [[Асимптотический закон распределения простых чисел]]
 
  
−
=== Практика - Вычисление <math>\pi(x)</math> ===
+
== 9 Лекция - Цепные (непрерывные) дроби и уравнение Пелля ==
 +
# [[Цепная дробь]]
 +
# [[Связь цепных дробей и алгоритма Евклида]]
 +
# [[Сходимость цепных дробей]]
 +
# [[Цепные дроби как приближение к числу]]
 +
# [[Квадратичная иррациональность]]
 +
# [[Периодичность цепных дробей]]
 +
# [[Цепные дроби для sqrtd и квадратичных иррациональностей|Цепные дроби для <tex>\sqrt{d}</tex> и квадратичных иррациональностей]]
 +
# [[Уравнение Пелля]]
 +
# [[Представление простых в виде суммы двух квадратов]]
  
−
== Лекция - Цепные (непрерывные) дроби и уравнение Пелля ==
+
<!--== Лекция - Конечные поля ==
−
* [[Цепная дробь]]
+
=== Практика - Методы разложения полиномов на множители над конечными полями ===-->
−
** [[Связь цепных дробей и алгоритма Евклида]]
 
−
** [[Сходимость цепных дробей]]
 
−
** [[Цепные дроби как приближение к числу]]
 
−
** [[Квадратичная иррациональность]]
 
−
** [[Периодичность цепных дробей]]
 
−
** [[Цепные дроби для sqrtd и квадратичных иррациональностей|Цепные дроби для <tex>\sqrt{d}</tex> и квадратичных иррациональностей]]
 
−
* [[Уравнение Пелля]]
 
−
* [[Представление простых в виде суммы двух квадратов]]
 
−
 
 
−
== Лекция - Конечные поля ==
 
−
=== Практика - Методы разложения полиномов на множители над конечными полями ===
 

Текущая версия на 19:03, 4 сентября 2022

Почти для всех конспектов есть одна большая правка: сделать конспект нормальным

1 Классы чисел и основная теорема арифметики

  1. Классы чисел 1-1,5
    1. увеличить дроби
    2. все формулы в тех
    3. источники информации добавить
    4. см также добавить
    5. английские термины
    6. заменить дефисы на тире, там где должно быть тире
    7. указать ссылки на основные статьи классов
  2. Натуральные и целые числа 5-10
    1. источники информации добавить
    2. см также добавить
    3. заменить дефисы на тире, там где должно быть тире
    4. Сделать нормальным
  3. Простые числа 2
    1. "Так как n делится на q, то n делится на a." показать формально
    2. поправить пунктуацию
    3. "Число N не делится ни на одно из простых чисел (2,3,5,…,p), так как при делении N на эти числа получится остаток 1." показать формально
  4. Наибольший общий делитель 2
    1. "Тогда gcd(a,b)=pmin(α1,β1)1⋅pmin(α2,β2)2⋅…⋅pmin(αk,βk)k" что такое p_i?
    2. Оформить правильно псевдокод
    3. заменить дефисы на тире, там где должно быть тире
    4. все формулы в тех
    5. второй пункт в лемме стандартного алгоритма Евклида переписать
  5. Основная теорема арифметики 2
    1. поместить в натуральные числа, нормально оформить
  6. Теоремы о простых числах 2
    1. переместить в конспект с простыми числами и нормально оформить
  7. Системы счисления 2
    1. Нормально заюзать тех
    2. источники информации добавить
    3. см также добавить
    4. английские термины
  8. Арифметика чисел в b-ичной системе счисления (Длинная арифметика) 5-8
    1. английские термины
    2. все формулы в тех
    3. категории
    4. источники информации
    5. см также
    6. знаки неравенств
    7. дроби
    8. добавить псевдокод
    9. сделать статью нормальной
  9. Разложение на множители (факторизация) 1-2
    1. знаки неравенств
    2. дефисы заменить на тире, там же должно быть тире
    3. английские термины
    4. сделать псевдокод одинаковым во всех частях статьи
    5. поправить статью

2 Лекция - Основные элементы теории чисел

  1. Сравнения, система вычетов, решение линейных систем по модулю 5-10-15
    1. поправить тех
    2. источники информации, см также
    3. сделать конспект нормальным
    4. разбить на 3 конспекта
  2. Китайская теорема об остатках 1-5
    1. поправить тех
    2. источники информации, см также
    3. добавить информации или поместить в конспект, где она должна быть теорема
  3. Теорема Ферма 1-5
    1. все правки из китайской теоремы об остатках
  4. Теорема Вильсона 1-5
    1. все правки из китайской теоремы об остатках
  5. Мультипликативность функции, свертка Дирихле 5-10
    1. разбить на 2, добавить информации
    2. поправить тех
    3. английские термины
    4. добавить использование шаблонов теорем/утверждений
  6. Функция Эйлера 1
    1. поправить тех
    2. английские термины
    3. добавить использование шаблонов терем/утверждений
    4. придать структуру
  7. Количество делителей, сумма делителей
  8. Функция Мебиуса
  1. Решето Эратосфена
  2. Быстрое возведение в степень
  3. Умножение по Монтгомери
  4. Дискретное преобразование Фурье
  5. Быстрое преобразование Фурье

3 Лекция - Основы теории групп

  1. Полугруппа, моноид, группа
  2. Абелева группа, Конечная группа
  3. Гомоморфизм групп, изоморфизм групп
  4. Подгруппа, нормальная подгруппа
  5. Порядок элемента группы, циклическая группа, конечно порожденная группа
  6. Регулярное представление группы
  7. Теорема о подгруппах циклической группы
  8. Смежные классы, теорема Лагранжа, факторгруппы
  9. Вычисление порядка элемента в группе
  10. Вычисление порядка перестановки в группе перестановок
  11. Дискретное логарифмирование в группе
  12. Действие группы на множестве
  13. Лемма Бернсайда, задача о числе ожерелий
  14. Представление групп

4 Лекция - Основы теории колец

  1. Определение кольца, подкольца, изоморфизмы колец
  2. Делители нуля, области целостности
  3. Единицы (обратимые элементы), группа обратимых элементов
  4. Неразложимые элементы, ассоциированные элементы и разложение на множители в целостных кольцах
  5. Евклидовы кольца

5 Лекция - Основы теории полей

  1. Определение поля и подполя, изоморфизмы полей
  2. Примеры полей
  3. Мультипликативная группа поля
  4. Расширения полей

6 Лекция - Первообразные корни и квадратичные вычеты

  1. Теорема о цикличности мультипликативной группы поля [math]\mathbb{Z}/p\mathbb{Z}[/math]
  2. Первообразные корни
  3. Теорема о существовании первообразных корней по модулям вида [math]2,4,p^n,2\cdot p^n[/math]
  4. Квадратичные вычеты, количество квадратичных вычетов по простому модулю
  5. Символ Лежандра, критерий Эйлера
  6. Теорема о [math]((\frac{p-1}{2})!)^2\equiv -1 (mod ~p)[/math] при [math]p=4\cdot k+1[/math]
  7. Лемма Гаусса для вычисления квадратичного характера числа по простому модулю

7 Лекция - Квадратичные вычеты

  1. Квадратичный закон взаимности
  2. Символ Якоби и его свойства
  3. Обобщенный квадратичный закон взаимности
  4. Алгоритм вычисления символа Якоби
  5. Тест Ферма проверки чисел на простоту, числа Кармайкла
  6. Тест Соловея-Штрассена
  7. Тест Миллера-Рабина

8 Лекция - Аналитическая теория чисел

  1. Факты из математического анализа
  2. Теорема Чебышёва
  3. Постулат Бертрана
  4. Уточнение констант в теореме Чебышёва
  5. Сумма обратных к простым
  6. Асимптотический закон распределения простых чисел


9 Лекция - Цепные (непрерывные) дроби и уравнение Пелля

  1. Цепная дробь
  2. Связь цепных дробей и алгоритма Евклида
  3. Сходимость цепных дробей
  4. Цепные дроби как приближение к числу
  5. Квадратичная иррациональность
  6. Периодичность цепных дробей
  7. Цепные дроби для [math]\sqrt{d}[/math] и квадратичных иррациональностей
  8. Уравнение Пелля
  9. Представление простых в виде суммы двух квадратов


Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теория_чисел:Тикеты&oldid=84346»