Маленькая теорема Ферма с помощью переставленных остатков Для простого числа p и целого числа, взаимно простого с p, умножьте каждый ненулевой остаток 1,...,p−1 на модуль p. Поскольку a обратимо по модулю p, это умножение просто переставляет ненулевые остатки, так что произведения всех слагаемых до и после совпадают. Это дает a ^{p−1}(p−1)! ≡ (p−1)! (по модулю p). Отменяем ненулевой коэффициент (p−1)! получаем ^{p−1} ≈ 1 (по модулю p).
Общая функция Эйлера как количество взаимно простых остатков Определите φ(n) как число целых чисел меньше n, которые являются взаимно простыми с n. Перечислите все вычеты R1,...,Rφ(n) по модулю n с gcd(Ri,n)=1, включая 1. Это как раз обратимые классы по модулю n и образуют основу для аргумента перестановки, аналогичного простому случаю.
Теорема Эйлера о перестановке остатков Для любого a, простого по отношению к n, остатки aR1,...,aRφ(n) уменьшаются по модулю n до чисел, все еще простых по отношению к n. Отсюда следует четкость, поскольку aRi ∈ aRj подразумевает Ri ∈ Rj. Следовательно, произведение a ^{φ(n)}R1...Rφ(n) ≡ R1...Rφ(n) (по модулю n), а отмена дает a^{φ(n)} ≡ 1 (по модулю n).
Подавление и отчетливость по модулю n Если aRi ∈ aRj (mod n) при gcd(a,n)=1, то a(Ri−Rj) ≡ 0 воздействует на n | (Ri−Rj), так что Ri ∈ Rj. Каждое значение aRi остается взаимно простым с n, поскольку новый общий делитель не появляется. Это подтверждает как перестановку множества, так и деление на ненулевое произведение.
Результат Ферма как частный случай Эйлера Для простого числа p φ (p) = p−1, поэтому теорема Эйлера сводится к малой теореме Ферма. То же доказательство перестановки остатков работает без изменений. Это объединяет простой и составной модули в рамках одного принципа.
Алгоритм Евклида идентифицирует нод Начните с a0=a и a1=b и выполните последовательные деления ai−2 = qi ai−1 + ai. Продолжайте до последнего ненулевого остатка, который равен gcd(a,b). Любой общий делитель a и b делит каждый остаток, и наоборот, поэтому конечной точкой является gcd.
Выражение gcd в виде линейной комбинации Изменяя последовательность деления, каждый остаток можно записать как линейную комбинацию двух предыдущих. В простом случае 6=4·1+2 получается 2=6-4, что уже является комбинацией исходных значений. Это иллюстрирует, как при обратной подстановке получаются целые числа x,y с ax+by=gcd(a,b).
Расширенный евклидов алгоритм Автоматизирует обратную замену После последнего шага деления инициализируйте пары коэффициентов и двигайтесь в обратном направлении, используя записанные частные для их обновления. На каждом шаге поддерживайте значение xi ai + yi ai+1 равным текущему остатку. Достижение начала дает x0 a + y0 b = gcd (a,b) без ручной алгебры.
Когда ax+by=c Имеет решения Пусть d=gcd(a,b). Если c не делится на d, то целочисленных решений не существует. Если c=kd, сначала найдите одну пару (x0,y0) с ax0+by=d, а затем умножьте на k, чтобы получить конкретное решение ax+by=c.
Все решения линейного диофантова уравнения Если (x1,y1) и (x2,y2) решают ax+by =d, то вычитание дает a(x1−x2)+b(y1−y2)=0. Это приводит к тому, что x1−x2 должно быть кратно b / d, а y1−y2 - кратно a/d. Следовательно, каждое решение равно x=x0 +(b/d) t, y=y0−(a/d) t с любым целым числом t, и масштабирование на k преобразует это в ax +by =c.
Квадратичные вычеты как быстрый тест на невозможность Чтобы исключить невозможные уравнения, сократите их по модулю до удобного простого числа и проверьте возможные квадратные остатки. Например, по модулю 5 остаток 3 никогда не бывает квадратным, поэтому любое условие, подразумевающее x ^ 2 ≡ 3 (по модулю 5), не имеет целочисленных решений. Этот простой фильтр часто мгновенно устраняет проблемы.
Квадратичные вычеты и символ Лежандра Для нечетного простого числа p и целого числа a назовем a квадратичным остатком по модулю p, если некоторое целое число x удовлетворяет x ^ 2 ∈ a (mod p); в противном случае это значение не является постоянным. Определите символ Лежандра (a/p) равным 0, если p делит a, 1, если a является остатком, и -1, если a является нерезидентом. Это сводит статус a к одному значению.
Ровно половина Ненулевых Классов Являются Квадратами Рассмотрим квадраты 1^2, 2^2, ..., ((p−1) /2) ^ 2 по модулю p. Каждый из них по определению является квадратичным вычетом, и никакие два из них не совпадают, потому что (i−j) (i+j) ≡ 0 (mod p) приводит к i=j при 1≤i+j
Отрицание Не добавляет Новых Квадратов Возведение в квадрат подчиняется x ^ 2 ≡ (p−x) ^ 2 по модулю p, поэтому остальные значения за пределами (p−1)/2 воспроизводят только один и тот же набор вычетов. Следовательно, другие ненулевые классы (p−1)/2 являются нерезидентами. Ноль - это квадрат, но он рассматривается отдельно.
Мультипликативность: тривиальные и прямоквадратичные случаи Если a≡0 или b≡0 (Mod р), то Ab≡0 и Лежандра символы умножают соответственно. Если оба A и B являются остатков, напишите≡х^2 и B≡М^2, значит АБ≡(ху)^2 снова остатка. Эти наблюдения устанавливают мультипликативность в простых случаях.
Остаток, умноженный на Нерезидентность, не может быть квадратом Предположим, что a∈x ^2 - это остаток, а b - нерезидент. Если бы ab был квадратом y ^2, то b∈y ^2·(x^2)^{-1} был бы квадратом, потому что x имеет модуль, обратный модулю p. Это противоречит тому, что b - иногородний, поэтому ab - иногородний.
Нерезидент Раз Нерезидент Должен быть квадратом Разделите ненулевые классы по модулю p на V (остатки) и N (нерезиденты), каждый из которых имеет размер (p−1)/2. Умножение каждого элемента из V на фиксированный нерезидент преобразует V в N, а умножение элементов из N на тот же нерезидент преобразует обратно в V. Следовательно, произведение двух нерезидентов лежит в V, т.е. является остатком.
Символ Лежандра является мультипликативным Все три случая вместе показывают, что (ab/p)=(a/p)(b/p) для всех целых чисел a и b по модулю p, включая нулевой случай. Это свойство будет сочетаться с критериями экспоненты для быстрого распознавания остатков. Это становится центральным вычислительным инструментом.
Критерий Эйлера: Распознавание квадратов по экспоненте Для нечетного простого числа p a является квадратичным вычетом по модулю p именно тогда, когда a ^{(p−1)/2} ≡ 1 (по модулю p). Нерезидент дает a ^{(p−1)/2} ≡ -1 (по модулю p). Это позволяет сопоставить символ Лежандра с простым тестом на экспоненту.
Вычеты дают единицу в соответствии с Маленькой теоремой Ферма Если a∈x^2, то a^{(p−1)/2}∈x^{p−1}. Малая теорема Ферма дает x^{p−1}∈1 по модулю p, потому что x не делится на p. Таким образом, остатки удовлетворяют положительной стороне критерия Эйлера.
Почему может отображаться только ±1 Для любого a, взаимно простого с p, Ферма утверждает, что a ^{p−1}≡1, поэтому (a^{(p−1)/2}-1)(a^{(p−1)/2}+1)≡0 по модулю p. Следовательно, значение a^{(p−1)/2} должно быть равно 1 или -1. Эта дихотомия соответствует разделению остатка на нерезиденты.
Отображение продуктов при умножении на нерезидента Пусть V - произведение всех остатков, а N - произведение всех нерезидентов. Если a − нерезидент, то при умножении каждого остатка на a набор остатков преобразуется в набор нерезидентов, что дает ^{(p-1)/2} V ∈ N по модулю p. Аналогично, умножение нерезидентов на a отображает обратное, поэтому умножение обеих сторон на V N дает ^ {(p−1) /2} V N ∈ N ^ 2.
Используя произведение всех ненулевых классов Суммарное произведение Vn равно произведению каждого ненулевого класса вычетов по модулю p, то есть (p−1)! по модулю p. По теореме Вильсона это произведение равно -1 по модулю p. Следовательно, a^{(p−1)/2} ≡ −N^2 по модулю p, когда a - нежилой фонд.
Незаконченный вывод для критерия Эйлера Чтобы завершить доказательство, осталось показать N ^ 2 ≈ 1 по модулю p, что привело бы к a ^{(p−1)/2} ≈ -1 для иногородних. Этот последний шаг был оставлен открытым и отложен для последующего завершения. Стратегия объединяет сопоставления множеств, факторные продукты и экспоненциальные тесты.