Сравнения, система вычетов, решение линейных систем по модулю — различия между версиями
Bochkarev (обсуждение | вклад) (→Теорема Вильсона) |
Bochkarev (обсуждение | вклад) (→Теорема Вильсона) |
||
Строка 58: | Строка 58: | ||
== Теорема Вильсона == | == Теорема Вильсона == | ||
− | '''p''' — простое <tex> \Leftrightarrow (p-1)! \equiv -1(mod \text{ }p)</tex> | + | |
− | + | ||
+ | {{Теорема | ||
+ | |id=thVilson | ||
+ | |author=Вильсон | ||
+ | |about=О простых числах | ||
+ | |statement= | ||
+ | '''p''' — простое <tex> \Leftrightarrow (p-1)! \equiv -1(mod \text{ }p)</tex>. | ||
+ | |proof= | ||
* <tex> \Leftarrow </tex> Если '''p''' — не простое, тогда <tex> (p-1)! \vdots p </tex> (кроме <tex> p = 4 </tex>),но -1, в любом случае, мы не получим. | * <tex> \Leftarrow </tex> Если '''p''' — не простое, тогда <tex> (p-1)! \vdots p </tex> (кроме <tex> p = 4 </tex>),но -1, в любом случае, мы не получим. | ||
* <tex> \Rightarrow </tex> Пусть <tex>x : 1 \le x \le p-1</tex>, для любого такого существует парный ему <tex> y</tex> такой, что <tex> xy \equiv 1(mod \text{ }p) </tex>. Может случиться, что для некоторых <math>x</math> будет выполнено равенство <tex>x=y</tex>. Тогда <tex> x^2 \equiv 1(mod \text{ }p) </tex>, значит <tex> (x-1)(x+1) \vdots p </tex>, значит <tex> x=1 </tex> или <tex>x=p-1</tex>. Таким образом последовательность <tex> 2,3, \ldots,p-2 </tex> разбивается на пары, что произведение чисел каждой из них сравнимо с 1 по модулю p. Таким образом <tex> (p-1)! \equiv 1(p-1)(mod \text{ }p)</tex>, откуда следует, что <tex> (p-1)! \equiv -1(mod \text{ }p)</tex> | * <tex> \Rightarrow </tex> Пусть <tex>x : 1 \le x \le p-1</tex>, для любого такого существует парный ему <tex> y</tex> такой, что <tex> xy \equiv 1(mod \text{ }p) </tex>. Может случиться, что для некоторых <math>x</math> будет выполнено равенство <tex>x=y</tex>. Тогда <tex> x^2 \equiv 1(mod \text{ }p) </tex>, значит <tex> (x-1)(x+1) \vdots p </tex>, значит <tex> x=1 </tex> или <tex>x=p-1</tex>. Таким образом последовательность <tex> 2,3, \ldots,p-2 </tex> разбивается на пары, что произведение чисел каждой из них сравнимо с 1 по модулю p. Таким образом <tex> (p-1)! \equiv 1(p-1)(mod \text{ }p)</tex>, откуда следует, что <tex> (p-1)! \equiv -1(mod \text{ }p)</tex> | ||
+ | }} |
Версия 01:50, 7 октября 2010
Содержание
Сравнения по модулю
Будем рассматривать целые числа в связи с остатками от деления их на данное целое число m, которое назовем модулем.
Каждому целому числу отвечает определенный остаток от деления его на m. Если двум целым a и b отвечает один и тот же остаток r, то они называются сравнимыми по модулю m.
Сравнимость для a и b записывается так :
Сравнимость чисел a и b по модулю m равносильна:
- 1. Возможности представить a в форме , где t - целое.
- 2. Делимости на m.
Арифметика сравнений
Свойства сравнений
- 1. Два числа, сравнимые с третьим сравнимы между собой.
- 2. Сравнения можно почленно складывать.
- 3. Сравнения можно почленно перемножать.
- 4. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.
- 5. Обе части сравнения можно умножить на одно и тоже число.
- 6. Обе части сравнения и модуль можно разделить на их общий делитель.
- 7. Если сравнение НОК этих модулей. имеет место по нескольким модулям, то оно имеет место и по модулю равному
- 8. Если сравнение имеет место по модулю m, то оно имеет место и по модулю d, равному любому делителю числа m.
- 9. Если одна часть сравнения и модуль делятся на некоторое число, то и другая сторона сравнения должна делится на это число.
- 10. Если , то .
Полная и приведенная система вычетов
Числа равноостаточные(сравнимые по модулю m) образуют класс чисел по модулю m.
Из такого определения следует, что всем числам класса отвечает один остаток r, и мы получим все числа класса,
если в форме
Любое число класса называется вычетом по модулю m. Вычет получаемый при , равный самому остатку r,
называется наименьшим неотрицательным вычетом.
Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по этому модулю.
Согласно 10-му свойству сравнений, числа одного класса по модулю m имеют одинаковый НОД. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим приведенную систему вычетов по модулю m.
Решение линейных систем по модулю
Пусть
Поиск решений:
,
Составим новое сравнение ,
обозначим его ,
его решением будет , где - числитель подходящей дроби.
Пусть
После этого решения исходного сравнения запишутся так :
Китайская теорема об остатках
Пусть
Неконструктивное доказательство :
, значит . То есть разных наборов всего n.
Теорема Ферма
, где p — простое. Доказательство.
- 1. , тогда, очевидно, .
- 2. Рассмотрим случай a не кратного p. Рассмотрим приведенную систему вычетов .
Система
задает те же вычеты, только в другом порядке, таким образом , сократив лишнее, получаем . Домножив обе части на a, получим теорему в изначально представленном виде.Теорема Вильсона
Теорема (Вильсон, О простых числах): |
p — простое . |
Доказательство: |
|