Лемма Гаусса (теория чисел) - Википедия - Gausss lemma (number theory)

Лемма Гаусса в теория чисел дает условие, чтобы целое число было квадратичный вычет. Хотя это бесполезно с вычислительной точки зрения, оно имеет теоретическое значение, поскольку участвует в некоторых доказательства квадратичной взаимности.

Впервые он появился в Карл Фридрих Гаусс третье доказательство (1808)^{[1]:458–462} из квадратичная взаимность и он снова доказал это в своем пятом доказательстве (1818 г.).^{[1]:496–501}

Утверждение леммы

Для любого нечетного простого числа п позволять а быть целым числом, которое совмещать к п.

Рассмотрим целые числа

${ displaystyle a, 2a, 3a, dots, { frac {p-1} {2}} a}$

и их наименьшие положительные вычеты по модулю п. (Все вычеты различны, поэтому имеется (п − 1)/2 их.)

Позволять п - количество этих остатков, превышающих п/2. потом

${ displaystyle left ({ frac {a} {p}} right) = (- 1) ^ {n},}$

куда ${ displaystyle left ({ frac {a} {p}} right)}$ это Символ Лежандра.

Пример

Принимая п = 11 и а = 7, соответствующая последовательность целых чисел

7, 14, 21, 28, 35.

После редукции по модулю 11 эта последовательность принимает вид

7, 3, 10, 6, 2.

Три из этих целых чисел больше 11/2 (а именно 6, 7 и 10), поэтому п = 3. Соответственно лемма Гаусса предсказывает, что

${ displaystyle left ({ frac {7} {11}} right) = (- 1) ^ {3} = - 1.}$

Это действительно правильно, потому что 7 не является квадратичным вычетом по модулю 11.

Вышеуказанная последовательность остатков

7, 3, 10, 6, 2

также может быть написано

−4, 3, −1, −5, 2.

В этой форме целые числа больше 11/2 отображаются как отрицательные числа. Также очевидно, что абсолютные значения остатков представляют собой перестановку остатков

1, 2, 3, 4, 5.

Доказательство

Довольно простое доказательство,^{[1]:458–462} напоминает один из самых простых доказательства малой теоремы Ферма, можно получить, оценив продукт

${ Displaystyle Z = а cdot 2a cdot 3a cdot cdots cdot { frac {p-1} {2}} а}$

по модулю п двумя разными способами. С одной стороны, это равно

${ Displaystyle Z = а ^ {(п-1) / 2} влево (1 CDOT 2 CDOT 3 CDOT CDOTS CDOT { гидроразрыва {р-1} {2}} right)}$

Вторая оценка требует больше работы. Если Икс является ненулевым вычетом по модулю п, определим «абсолютное значение» Икс быть

${ displaystyle | x | = { begin {case} x & { mbox {if}} 1 leq x leq { frac {p-1} {2}}, p-x & { mbox {если }} { frac {p + 1} {2}} leq x leq p-1. end {case}}}$

С п считает эти кратные ка которые находятся в последнем диапазоне, и поскольку для этих кратных −ка находится в первом диапазоне, мы имеем

${ Displaystyle Z = (- 1) ^ {n} left (| a | cdot | 2a | cdot | 3a | cdot cdots cdots left | { frac {p-1} {2}} a right | right).}$

Теперь заметьте, что значения |ра| находятся отчетливый за р = 1, 2, …, (п − 1)/2. Действительно, у нас есть

${ displaystyle { begin {align} | ra | & Equiv | sa | & { pmod {p}} ra & Equiv pm sa & { pmod {p}} r & Equiv pm s & { pmod {p}} конец {выровнено}}}$

потому что а взаимно прост с п.

Это дает р = s, поскольку р и s положительные наименьшие вычеты. Но есть точно (п − 1)/2 из них, поэтому их значения представляют собой перестановку целых чисел 1, 2, …, (п − 1)/2. Следовательно,

${ displaystyle Z = (- 1) ^ {n} left (1 cdot 2 cdot 3 cdot cdots cdot { frac {p-1} {2}} right).}$

Сравнивая с нашей первой оценкой, мы можем исключить ненулевой множитель

${ displaystyle 1 cdot 2 cdot 3 cdot cdots cdot { frac {p-1} {2}}}$

и мы остались с

${ displaystyle a ^ {(p-1) / 2} = (- 1) ^ {n}.}$

Это желаемый результат, потому что по Критерий Эйлера левая часть - просто альтернативное выражение для символа Лежандра ${ displaystyle left ({ frac {a} {p}} right)}$.

Приложения

Лемма Гаусса используется во многих,^{[2]:Гл. 1[2]:9} но далеко не все из известных доказательств квадратичной взаимности.

Например, Готтхольд Эйзенштейн^[2]:236 использовал лемму Гаусса, чтобы доказать, что если п нечетное простое число, тогда

${ displaystyle left ({ frac {a} {p}} right) = prod _ {n = 1} ^ {(p-1) / 2} { frac { sin {(2 pi an / p)}} { sin {(2 pi n / p)}}},}$

и использовал эту формулу для доказательства квадратичной взаимности. Используя эллиптический скорее, чем круговой функций, он доказал кубический и четверная взаимность законы.^{[2]:Гл. 8}

Леопольд Кронекер^{[2]:Бывший. 1,34} использовал лемму, чтобы показать, что

${ displaystyle left ({ frac {p} {q}} right) = operatorname {sgn} prod _ {i = 1} ^ { frac {q-1} {2}} prod _ { k = 1} ^ { frac {p-1} {2}} left ({ frac {k} {p}} - { frac {i} {q}} right).}$

Переключение п и q сразу дает квадратичную взаимность.

Он также используется в, вероятно, самых простых доказательствах «второго дополнительного закона».

${ displaystyle left ({ frac {2} {p}} right) = (- 1) ^ {(p ^ {2} -1) / 8} = { begin {case} +1 { text {если}} p Equiv pm 1 { pmod {8}} - 1 { text {if}} p Equiv pm 3 { pmod {8}} end {case}}}$

Высшие силы

Обобщения леммы Гаусса можно использовать для вычисления символов вычета более высокой степени. В своей второй монографии о биквадратичной взаимности,^{[3]:§§69–71} Гаусс использовал лемму о четвертой степени, чтобы получить формулу для биквадратичного характера 1 + я в Z[я], кольцо Гауссовские целые числа. Впоследствии Эйзенштейн использовал версии в третьей и четвертой степени, чтобы доказать кубический и четверная взаимность.^{[2]:Гл. 8}

псимвол остатка степени

Позволять k быть поле алгебраических чисел с кольцо целых чисел ${ displaystyle { mathcal {O}} _ {k},}$ и разреши ${ Displaystyle { mathfrak {p}} subset { mathcal {O}} _ {k}}$ быть главный идеал. В идеальная норма ${ Displaystyle mathrm {N} { mathfrak {p}}}$ из ${ Displaystyle { mathfrak {p}}}$ определяется как мощность кольца классов вычетов. С ${ Displaystyle { mathfrak {p}}}$ простое это конечное поле ${ displaystyle { mathcal {O}} _ {k} / { mathfrak {p}}}$, поэтому идеальная норма ${ Displaystyle mathrm {N} { mathfrak {p}} = | { mathcal {O}} _ {k} / { mathfrak {p}} |}$.

Предположим, что примитивный пth корень единства ${ displaystyle zeta _ {n} in { mathcal {O}} _ {k},}$ и это п и ${ Displaystyle { mathfrak {p}}}$ находятся совмещать (т.е. ${ displaystyle n not in { mathfrak {p}}}$). Тогда нет двух разных пкорни из единицы могут быть сравнимы по модулю ${ Displaystyle { mathfrak {p}}}$.

Это можно доказать от противного, начиная с предположения, что ${ Displaystyle дзета _ {п} ^ {г} экв дзета _ {п} ^ {s}}$ мод ${ Displaystyle { mathfrak {p}}}$, 0 < р < s ≤ п. Позволять т = s − р такой, что ${ Displaystyle zeta _ {п} ^ {т} эквив 1}$ мод ${ Displaystyle { mathfrak {p}}}$, и 0 < т < п. Из определения корней единства

${ displaystyle x ^ {n} -1 = (x-1) (x- zeta _ {n}) (x- zeta _ {n} ^ {2}) dots (x- zeta _ {n } ^ {n-1}),}$

и деление на Икс − 1 дает

${ displaystyle x ^ {n-1} + x ^ {n-2} + точки + x + 1 = (x- zeta _ {n}) (x- zeta _ {n} ^ {2}) точки (x- zeta _ {n} ^ {n-1}).}$

Сдача Икс = 1 и взяв остатки мода ${ Displaystyle { mathfrak {p}}}$,

${ Displaystyle п эквив (1- дзета _ {п}) (1- дзета _ {п} ^ {2}) точки (1- дзета _ {п} ^ {п-1}) { pmod { mathfrak {p}}}.}$

С п и ${ Displaystyle { mathfrak {p}}}$ взаимно просты, ${ Displaystyle п не эквив 0}$ мод ${ displaystyle { mathfrak {p}},}$ но согласно предположению, один из факторов справа должен быть равен нулю. Следовательно, предположение, что два различных корня конгруэнтны, неверно.

Таким образом, классы вычетов ${ displaystyle { mathcal {O}} _ {k} / { mathfrak {p}}}$ содержащий полномочия ζ_п являются подгруппой порядка п своей (мультипликативной) группы единиц, ${ displaystyle ({ mathcal {O}} _ {k} / { mathfrak {p}}) ^ { times} = { mathcal {O}} _ {k} / { mathfrak {p}} - {0 }.}$ Следовательно, порядок ${ displaystyle ({ mathcal {O}} _ {k} / { mathfrak {p}}) ^ { times}}$ кратно п, и

${ displaystyle { begin {align} mathrm {N} { mathfrak {p}} & = | { mathcal {O}} _ {k} / { mathfrak {p}} | & = left | ({ mathcal {O}} _ {k} / { mathfrak {p}}) ^ { times} right | +1 & Equiv 1 { pmod {n}}. end {выровнено }}}$

Аналог теоремы Ферма есть в ${ displaystyle { mathcal {O}} _ {k}}$. Если ${ displaystyle alpha in { mathcal {O}} _ {k}}$ за ${ displaystyle alpha not in { mathfrak {p}}}$, тогда^{[2]:Гл. 4.1}

${ Displaystyle альфа ^ { mathrm {N} { mathfrak {p}} - 1} Equiv 1 { pmod { mathfrak {p}}},}$

и с тех пор ${ Displaystyle mathrm {N} { mathfrak {p}} эквив 1}$ мод п,

${ Displaystyle alpha ^ { frac { mathrm {N} { mathfrak {p}} - 1} {n}} Equiv zeta _ {n} ^ {s} { pmod { mathfrak {p} }}}$

хорошо определен и конгруэнтен уникальному пкорень -й степени из единицы ζ_п^s.

Этот корень единства называется псимвол остатка степени th для ${ displaystyle { mathcal {O}} _ {k},}$ и обозначается

${ displaystyle { begin {align} left ({ frac { alpha} { mathfrak {p}}} right) _ {n} & = zeta _ {n} ^ {s} & Equiv alpha ^ { frac { mathrm {N} { mathfrak {p}} - 1} {n}} { pmod { mathfrak {p}}}. end {выравнивается}}}$

Можно доказать, что^{[2]:Предложение 4.1}

${ displaystyle left ({ frac { alpha} { mathfrak {p}}} right) _ {n} = 1}$

если и только если есть ${ displaystyle eta in { mathcal {O}} _ {k}}$ такой, что α ≡ η^п мод ${ Displaystyle { mathfrak {p}}}$.

1/п системы

Позволять ${ displaystyle mu _ {n} = {1, zeta _ {n}, zeta _ {n} ^ {2}, dots, zeta _ {n} ^ {n-1} }}$ - мультипликативная группа пкорни единства, и пусть ${ displaystyle A = {a_ {1}, a_ {2}, dots, a_ {m} }}$ быть представителями смежных классов ${ displaystyle ({ mathcal {O}} _ {k} / { mathfrak {p}}) ^ { times} / mu _ {n}.}$ потом А называется 1/п система мод ${ displaystyle { mathfrak {p}}.}$^{[2]:Гл. 4.2}

Другими словами, есть ${ displaystyle mn = mathrm {N} { mathfrak {p}} - 1}$ числа в наборе ${ displaystyle A mu = {a_ {i} zeta _ {n} ^ {j} ;: ; 1 leq i leq m, ; ; ; 0 leq j leq n- 1 },}$ и этот набор представляет собой репрезентативный набор для ${ displaystyle ({ mathcal {O}} _ {k} / { mathfrak {p}}) ^ { times}.}$

Цифры 1, 2, … (п − 1)/2, использованные в исходной версии леммы, представляют собой систему 1/2 (mod п).

Строительство 1/п система проста: пусть M быть представительным набором для ${ displaystyle ({ mathcal {O}} _ {k} / { mathfrak {p}}) ^ { times}.}$ Выберите любой ${ displaystyle a_ {1} in M}$ и удалите числа, соответствующие ${ displaystyle a_ {1}, a_ {1} zeta _ {n}, a_ {1} zeta _ {n} ^ {2}, dots, a_ {1} zeta _ {n} ^ {n -1}}$ из M. Выбирать а₂ из M и удалите числа, соответствующие ${ displaystyle a_ {2}, a_ {2} zeta _ {n}, a_ {2} zeta _ {n} ^ {2}, dots, a_ {2} zeta _ {n} ^ {n -1}}$ Повторяйте до тех пор, пока M истощен. потом {а₁, а₂, … а_м} это 1/п системный мод ${ displaystyle { mathfrak {p}}.}$

Лемма для псилы

Лемму Гаусса можно распространить на псимвол остатка мощности следующим образом.^{[2]:Предложение 4.3} Позволять ${ displaystyle zeta _ {n} in { mathcal {O}} _ {k}}$ быть примитивным пй корень единства, ${ Displaystyle { mathfrak {p}} subset { mathcal {O}} _ {k}}$ главный идеал, ${ displaystyle gamma in { mathcal {O}} _ {k}, ; ; n gamma not in { mathfrak {p}},}$ (т.е. ${ Displaystyle { mathfrak {p}}}$ взаимно прост с обоими γ и п) и разреши А = {а₁, а₂, …, а_м} быть 1/п системный мод ${ displaystyle { mathfrak {p}}.}$

Тогда для каждого я, 1 ≤ я ≤ м, есть целые числа π(я), уникальный (мод м), и б(я), уникальный (мод п), такое что

${ Displaystyle гамма а_ {я} экв дзета _ {п} ^ {б (я)} а _ { пи (я)} { pmod { mathfrak {p}}},}$

и пСимвол остатка в степени -й степени задается формулой

${ displaystyle left ({ frac { gamma} { mathfrak {p}}} right) _ {n} = zeta _ {n} ^ {b (1) + b (2) + dots + b (m)}.}$

Классическая лемма для квадратичного символа Лежандра является частным случаем п = 2, ζ₂ = −1, А = {1, 2, …, (п − 1)/2}, б(k) = 1 если ак > п/2, б(k) = 0 если ак < п/2.

Доказательство

Доказательство пВ лемме-степени используются те же идеи, что и при доказательстве квадратичной леммы.

Существование целых чисел π(я) и б(я), и их уникальность (мод м) и (мод п) соответственно вытекают из того, что Aμ представляет собой репрезентативный набор.

Предположить, что π(я) = π(j) = п, т.е.

${ Displaystyle гамма а_ {я} экв дзета _ {п} ^ {г} а_ {р} { pmod { mathfrak {р}}}}$

и

${ displaystyle gamma a_ {j} Equiv zeta _ {n} ^ {s} a_ {p} { pmod { mathfrak {p}}}.}$

потом

${ displaystyle zeta _ {n} ^ {sr} gamma a_ {i} Equiv zeta _ {n} ^ {s} a_ {p} Equiv gamma a_ {j} { pmod { mathfrak { п}}}}$

Потому что γ и ${ Displaystyle { mathfrak {p}}}$ взаимно просты, обе стороны делятся на γ, давая

${ displaystyle zeta _ {n} ^ {s-r} a_ {i} Equiv a_ {j} { pmod { mathfrak {p}}},}$

который, поскольку А это 1/п система, подразумевает s = р и я = j, показывая, что π является перестановкой множества {1, 2, …, м}.

Тогда, с одной стороны, по определению символа степенного вычета,

${ Displaystyle { begin {align} ( gamma a_ {1}) ( gamma a_ {2}) dots ( gamma a_ {m}) & = gamma ^ { frac { mathrm {N} { mathfrak {p}} - 1} {n}} a_ {1} a_ {2} dots a_ {m} & Equiv left ({ frac { gamma} { mathfrak {p}}} right) _ {n} a_ {1} a_ {2} dots a_ {m} { pmod { mathfrak {p}}}, end {align}}}$

а с другой стороны, поскольку π это перестановка,

${ Displaystyle { begin {align} ( gamma a_ {1}) ( gamma a_ {2}) dots ( gamma a_ {m}) & Equiv { zeta _ {n} ^ {b (1 )} a _ { pi (1)}} { zeta _ {n} ^ {b (2)} a _ { pi (2)}} dots { zeta _ {n} ^ {b (m)} a _ { pi (m)}} & { pmod { mathfrak {p}}} & Equiv zeta _ {n} ^ {b (1) + b (2) + dots + b (m )} a _ { pi (1)} a _ { pi (2)} dots a _ { pi (m)} & { pmod { mathfrak {p}}} & Equiv zeta _ {n } ^ {b (1) + b (2) + dots + b (m)} a_ {1} a_ {2} dots a_ {m} & { pmod { mathfrak {p}}}, end {выровнено}}}$

так

${ displaystyle left ({ frac { gamma} { mathfrak {p}}} right) _ {n} a_ {1} a_ {2} dots a_ {m} Equiv zeta _ {n} ^ {b (1) + b (2) + dots + b (m)} a_ {1} a_ {2} dots a_ {m} { pmod { mathfrak {p}}},}$

и поскольку для всех 1 ≤ я ≤ м, а_я и ${ Displaystyle { mathfrak {p}}}$ взаимно просты, а₁а₂…а_м может быть отменено с обеих сторон сравнения,

${ displaystyle left ({ frac { gamma} { mathfrak {p}}} right) _ {n} Equiv zeta _ {n} ^ {b (1) + b (2) + dots + b (m)} { pmod { mathfrak {p}}},}$

и теорема следует из того, что нет двух различных пкорни из единицы могут быть конгруэнтными (mod ${ Displaystyle { mathfrak {p}}}$).

Отношение к переносу в теории групп

Позволять грамм - мультипликативная группа ненулевых классов вычетов в Z/пZ, и разреши ЧАС - подгруппа {+1, −1}. Рассмотрим следующие представители смежного класса ЧАС в грамм,

${ displaystyle 1,2,3, dots, { frac {p-1} {2}}.}$

Применяя технику передача к этому набору представителей смежных классов получаем гомоморфизм переноса

${ displaystyle phi: G to H,}$

которая оказывается картой, отправляющей а к (−1)^п, куда а и п такие же, как в формулировке леммы. Тогда лемму Гаусса можно рассматривать как вычисление, которое явно идентифицирует этот гомоморфизм как характер квадратичного вычета.

Смотрите также

Две другие характеристики квадратов по простому модулю: Критерий Эйлера и Лемма Золотарева.

Рекомендации