Теорема Ферма о суммах двух квадратов

Условие, при котором нечетное простое число является суммой двух квадратов

В теории аддитивных чисел теорема Ферма о суммах двух квадратов утверждает, что нечетное простое число p можно выразить как:

${\displaystyle p=x^{2}+y^{2},}$

с целыми числами x и y , тогда и только тогда, когда

${\displaystyle p\equiv 1{\pmod {4}}.}$

Простые числа, для которых это верно, называются пифагорейскими простыми числами . Например, простые числа 5, 13, 17, 29, 37 и 41 все сравнимы с 1 по модулю 4, и их можно выразить как суммы двух квадратов следующими способами:

${\displaystyle 5=1^{2}+2^{2},\quad 13=2^{2}+3^{2},\quad 17=1^{2}+4^{2},\quad 29=2^{2}+5^{2},\quad 37=1^{2}+6^{2},\quad 41=4^{2}+5^{2}.}$

С другой стороны, простые числа 3, 7, 11, 19, 23 и 31 все сравнимы с 3 по модулю 4, и ни одно из них не может быть выражено как сумма двух квадратов. Это более легкая часть теоремы, и она немедленно следует из наблюдения, что все квадраты сравнимы с 0 (если квадрат числа четный) или 1 (если квадрат числа нечетный) по модулю 4.

Поскольку тождество Диофанта подразумевает, что произведение двух целых чисел, каждое из которых может быть записано как сумма двух квадратов, само выражается как сумма двух квадратов, применяя теорему Ферма к разложению на простые множители любого положительного целого числа n , мы видим, что если все простые множители числа n, сравнимые с 3 по модулю 4, имеют четную степень, то n выражается как сумма двух квадратов. Обратное также верно. ^[1] Это обобщение теоремы Ферма известно как теорема о сумме двух квадратов .

История

Альбер Жирар был первым, кто сделал это наблюдение, охарактеризовав положительные целые числа (не обязательно простые), которые можно представить в виде суммы двух квадратов положительных целых чисел; это было опубликовано в 1625 году. ^{[2] [3]} Утверждение о том, что каждое простое число p вида 4n+1 является суммой двух квадратов, иногда называют теоремой Жирара . ^[4] Со своей стороны, Ферма написал подробную версию утверждения (в которой он также указал число возможных выражений степеней числа p в виде суммы двух квадратов) в письме к Марену Мерсенну от 25 декабря 1640 года: по этой причине эту версию теоремы иногда называют рождественской теоремой Ферма.

Гауссовы простые числа

Теорема Ферма о суммах двух квадратов тесно связана с теорией гауссовых простых чисел .

Гауссово целое число — это комплексное число , такое что a и b — целые числа. Норма гауссова целого числа — это целое число, равное квадрату абсолютного значения гауссова целого числа. Норма произведения гауссовских целых чисел — это произведение их норм. Это тождество Диофанта , которое немедленно следует из аналогичного свойства абсолютного значения. ${\displaystyle a+ib}$ ${\displaystyle N(a+ib)=a^{2}+b^{2}}$

Гауссовские целые числа образуют главную идеальную область . Это подразумевает, что гауссовские простые числа могут быть определены аналогично простым числам, то есть как те гауссовские целые числа, которые не являются произведением двух неединиц (здесь единицами являются 1, −1, i и − i ).

Мультипликативное свойство нормы подразумевает, что простое число p является либо гауссовым простым числом, либо нормой гауссового простого числа. Теорема Ферма утверждает, что первый случай имеет место, когда и что второй случай имеет место, когда и Последний случай не рассматривается в утверждении Ферма, но является тривиальным, так как ${\displaystyle p=4k+3,}$ ${\displaystyle p=4k+1}$ ${\displaystyle p=2.}$ ${\displaystyle 2=1^{2}+1^{2}=N(1+i).}$

Связанные результаты

Вышеизложенная точка зрения на теорему Ферма является частным случаем теории факторизации идеалов в кольцах целых квадратичных чисел . Подводя итог, если — кольцо целых алгебраических чисел в квадратичном поле , то нечетное простое число p , не делящее d , является либо простым элементом в , либо идеальной нормой идеала, который обязательно является простым. Более того, закон квадратичной взаимности позволяет различать эти два случая в терминах сравнений. Если — область главных идеалов , то p является идеальной нормой тогда и только тогда, когда ${\displaystyle {\mathcal {O}}_{\sqrt {d}}}$ ${\displaystyle {\mathcal {O}}_{\sqrt {d}},}$ ${\displaystyle {\mathcal {O}}_{\sqrt {d}},}$ ${\displaystyle {\mathcal {O}}_{\sqrt {d}}}$

${\displaystyle 4p=a^{2}-db^{2},}$

где a и b — оба целые числа.

В письме Блезу Паскалю от 25 сентября 1654 года Ферма объявил о следующих двух результатах, которые по сути являются частными случаями : Если p — нечетное простое число, то ${\displaystyle d=-2}$ ${\displaystyle d=-3.}$

${\displaystyle p=x^{2}+2y^{2}\iff p\equiv 1{\mbox{ or }}p\equiv 3{\pmod {8}},}$

${\displaystyle p=x^{2}+3y^{2}\iff p\equiv 1{\pmod {3}}.}$

Ферма также писал:

Если перемножить два простых числа, оканчивающихся на 3 или 7 и превосходящих на 3 число, кратное 4, то их произведение будет состоять из квадрата и пятерки другого квадрата.

Другими словами, если p, q имеют вид 20 k + 3 или 20 k + 7 , то pq = x ² + 5 y ^2. Позже Эйлер расширил это до гипотезы, что

${\displaystyle p=x^{2}+5y^{2}\iff p\equiv 1{\mbox{ or }}p\equiv 9{\pmod {20}},}$

${\displaystyle 2p=x^{2}+5y^{2}\iff p\equiv 3{\mbox{ or }}p\equiv 7{\pmod {20}}.}$

И утверждение Ферма, и гипотеза Эйлера были установлены Жозефом-Луи Лагранжем . Эта более сложная формулировка основана на том факте, что не является областью главных идеалов, в отличие от и ${\displaystyle {\mathcal {O}}_{\sqrt {-5}}}$ ${\displaystyle {\mathcal {O}}_{\sqrt {-2}}}$ ${\displaystyle {\mathcal {O}}_{\sqrt {-3}}.}$

Алгоритм

Существует тривиальный алгоритм разложения простого числа вида на сумму двух квадратов: Для всех n таких , проверьте, является ли квадратный корень целым числом. Если это так, то разложение получено. ${\displaystyle p=4k+1}$ ${\displaystyle 1\leq n<{\sqrt {p}}}$ ${\displaystyle p-n^{2}}$

Однако размер входных данных алгоритма равен количеству цифр числа p (с точностью до постоянного множителя, зависящего от основания системы счисления ). Количество необходимых тестов имеет порядок и, таким образом, экспоненциально зависит от размера входных данных. Таким образом, вычислительная сложность этого алгоритма экспоненциальна . ${\displaystyle \log p,}$ ${\displaystyle {\sqrt {p}}=\exp \left({\frac {\log p}{2}}\right),}$

Алгоритм Лас-Вегаса с вероятностно- полиномиальной сложностью был описан Стэном Вагоном в 1990 году на основе работ Серрета и Эрмита (1848) и Корнаккии (1908). ^[5] Вероятностная часть состоит в нахождении квадратичного невычета, что может быть сделано с вероятностью успеха , а затем итерировано в случае неудачи. Условно это также может быть сделано за детерминированное полиномиальное время, если обобщенная гипотеза Римана верна, как объяснено для алгоритма Тонелли–Шэнкса . ${\displaystyle \approx {\frac {1}{2}}}$

Описание

Дано нечетное простое число в форме , сначала найдите такое, что . Это можно сделать, найдя квадратичный невычет по модулю , скажем , и положив . ${\displaystyle p}$ ${\displaystyle 4k+1}$ ${\displaystyle x}$ ${\displaystyle x^{2}\equiv -1{\pmod {p}}}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle x=q^{\frac {p-1}{4}}{\pmod {p}}}$

Такой будет удовлетворять условию, поскольку квадратичные невычеты удовлетворяют . ${\displaystyle x}$ ${\displaystyle q^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}$

После определения можно применить алгоритм Евклида с и . Обозначим первые два остатка, которые меньше квадратного корня, как и . Тогда будет так, что . ${\displaystyle x}$ ${\displaystyle p}$ ${\displaystyle x}$ ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a^{2}+b^{2}=p}$

Пример

Возьмем . Возможный квадратичный невычет для 97 равен 13, так как . поэтому мы позволяем . Алгоритм Евклида, примененный к 97 и 22, дает: Первые два остатка, меньшие квадратного корня из 97, равны 9 и 4; и действительно, мы имеем , как и ожидалось. ${\displaystyle p=97}$ ${\displaystyle 13^{\frac {97-1}{2}}\equiv -1{\pmod {97}}}$ ${\displaystyle x=13^{\frac {97-1}{4}}=22{\pmod {97}}}$ $${\displaystyle 97=22(4)+9,}$$ $${\displaystyle 22=9(2)+4,}$$ $${\displaystyle 9=4(2)+1,}$$ $${\displaystyle 4=1(4).}$$ ${\displaystyle 97=9^{2}+4^{2}}$

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

Ферма обычно не записывал доказательства своих утверждений, и он не предоставил доказательство этого утверждения. Первое доказательство было найдено Эйлером после больших усилий и основано на бесконечном спуске . Он объявил об этом в двух письмах Гольдбаху , 6 мая 1747 года и 12 апреля 1749 года; он опубликовал подробное доказательство в двух статьях (между 1752 и 1755 годами). ^{[6] [7]} Лагранж дал доказательство в 1775 году, которое было основано на его изучении квадратичных форм . Это доказательство было упрощено Гауссом в его Disquisitiones Arithmeticae (статья 182). Дедекинд дал по крайней мере два доказательства, основанных на арифметике гауссовых целых чисел . Существует элегантное доказательство, использующее теорему Минковского о выпуклых множествах. Упростив более раннее короткое доказательство, предложенное Хит-Брауном (который был вдохновлен идеей Лиувилля ), Загир в 1990 году представил неконструктивное доказательство из одного предложения . ^[8] А совсем недавно Кристофер дал доказательство на основе теории разбиений . ^[9]

Доказательство Эйлера методом бесконечного спуска

Эйлеру удалось доказать теорему Ферма о суммах двух квадратов в 1749 году, когда ему было сорок два года. Он сообщил об этом в письме Гольдбаху от 12 апреля 1749 года. ^[10] Доказательство основано на бесконечном спуске и лишь кратко изложено в письме. Полное доказательство состоит из пяти шагов и опубликовано в двух статьях. Первые четыре шага являются предложениями 1–4 первой статьи ^[11] и не соответствуют в точности четырем шагам ниже. Пятый шаг ниже взят из второй статьи. ^{[12] [13]}

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

1. Произведение двух чисел, каждое из которых является суммой двух квадратов, само является суммой двух квадратов.

Это хорошо известное свойство, основанное на идентичности

${\displaystyle (a^{2}+b^{2})(p^{2}+q^{2})=(ap+bq)^{2}+(aq-bp)^{2}}$

благодаря Диофанту .

2. Если число, являющееся суммой двух квадратов, делится на простое число, являющееся суммой двух квадратов, то частное является суммой двух квадратов. (Это первое предложение Эйлера).

Действительно, предположим, например, что делится на и что это последнее является простым числом. Тогда делится ${\displaystyle a^{2}+b^{2}}$ ${\displaystyle p^{2}+q^{2}}$ ${\displaystyle p^{2}+q^{2}}$

${\displaystyle (pb-aq)(pb+aq)=p^{2}b^{2}-a^{2}q^{2}=p^{2}(a^{2}+b^{2})-a^{2}(p^{2}+q^{2}).}$

Так как является простым числом, то оно делит один из двух множителей. Предположим, что оно делит . Так как ${\displaystyle p^{2}+q^{2}}$ ${\displaystyle pb-aq}$

${\displaystyle (a^{2}+b^{2})(p^{2}+q^{2})=(ap+bq)^{2}+(aq-bp)^{2}}$

(тождество Диофанта) следует, что должно делить . Таким образом, уравнение можно разделить на квадрат . Деление выражения на дает: ${\displaystyle p^{2}+q^{2}}$ ${\displaystyle (ap+bq)^{2}}$ ${\displaystyle p^{2}+q^{2}}$ ${\displaystyle (p^{2}+q^{2})^{2}}$

${\displaystyle {\frac {a^{2}+b^{2}}{p^{2}+q^{2}}}=\left({\frac {ap+bq}{p^{2}+q^{2}}}\right)^{2}+\left({\frac {aq-bp}{p^{2}+q^{2}}}\right)^{2}}$

и таким образом выражает частное как сумму двух квадратов, как и утверждается.

С другой стороны, если делит , то аналогичное рассуждение справедливо с использованием следующего варианта тождества Диофанта: ${\displaystyle p^{2}+q^{2}}$ ${\displaystyle pb+aq}$

${\displaystyle (a^{2}+b^{2})(q^{2}+p^{2})=(aq+bp)^{2}+(ap-bq)^{2}.}$

3. Если число, которое можно записать в виде суммы двух квадратов, делится на число, которое не является суммой двух квадратов, то частное имеет множитель, который не является суммой двух квадратов. (Это второе предложение Эйлера).

Предположим, что есть число, не выраженное в виде суммы двух квадратов, которое делит . Запишите частное, разложенное на его (возможно, повторяющиеся) простые множители, как так, что . Если все множители можно записать в виде суммы двух квадратов, то мы можем последовательно разделить на , и т. д., и применяя шаг (2.) выше, мы выводим, что каждое последующее, меньшее, частное является суммой двух квадратов. Если мы дойдем до , то само должно было бы быть равно сумме двух квадратов, что является противоречием. Таким образом, по крайней мере одно из простых чисел не является суммой двух квадратов. ${\displaystyle q}$ ${\displaystyle a^{2}+b^{2}}$ ${\displaystyle p_{1}p_{2}\cdots p_{n}}$ ${\displaystyle a^{2}+b^{2}=qp_{1}p_{2}\cdots p_{n}}$ ${\displaystyle p_{i}}$ ${\displaystyle a^{2}+b^{2}}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle p_{i}}$

4. Если и являются взаимно простыми положительными целыми числами, то каждый множитель является суммой двух квадратов. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a^{2}+b^{2}}$ (Это шаг, который использует шаг (3) для получения «бесконечного спуска» и был Предложением Эйлера 4. Доказательство, набросок которого приведен ниже, также включает доказательство его Предложения 3).

Пусть будут взаимно простыми положительными целыми числами: без потери общности само по себе не является простым, иначе нечего доказывать. Пусть поэтому будет собственным множителем , не обязательно простым: мы хотим показать, что является суммой двух квадратов. Опять же, мы ничего не теряем, предполагая, поскольку случай очевиден. ${\displaystyle a,b}$ ${\displaystyle a^{2}+b^{2}}$ ${\displaystyle q}$ ${\displaystyle a^{2}+b^{2}}$ ${\displaystyle q}$ ${\displaystyle q>2}$ ${\displaystyle q=2=1^{2}+1^{2}}$

Пусть будут неотрицательными целыми числами, такими, что являются ближайшими кратными (по абсолютной величине) к соответственно. Обратите внимание, что разности и являются целыми числами с абсолютной величиной, строго меньшей : действительно, когда четно, gcd ; в противном случае, поскольку gcd , мы также имели бы gcd . ${\displaystyle m,n}$ ${\displaystyle mq,nq}$ ${\displaystyle q}$ ${\displaystyle a,b}$ ${\displaystyle c=a-mq}$ ${\displaystyle d=b-nq}$ ${\displaystyle q/2}$ ${\displaystyle q>2}$ ${\displaystyle (a,q/2)=1}$ ${\displaystyle (a,q/2)\mid q/2\mid q\mid a^{2}+b^{2}}$ ${\displaystyle (a,q/2)\mid b}$

Умножая получаем

${\displaystyle a^{2}+b^{2}=m^{2}q^{2}+2mqc+c^{2}+n^{2}q^{2}+2nqd+d^{2}=Aq+(c^{2}+d^{2})}$

однозначно определяя неотрицательное целое число . Поскольку делит оба конца этой последовательности уравнений, следует, что также должно делиться на : скажем . Пусть будет наибольшим общим делителем и , который в силу взаимной простоты является взаимно простым с . Таким образом , делит , поэтому, записывая , и , мы получаем выражение для взаимно простых и , и с , поскольку ${\displaystyle A}$ ${\displaystyle q}$ ${\displaystyle c^{2}+d^{2}}$ ${\displaystyle q}$ ${\displaystyle c^{2}+d^{2}=qr}$ ${\displaystyle g}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle a,b}$ ${\displaystyle q}$ ${\displaystyle g^{2}}$ ${\displaystyle r}$ ${\displaystyle e=c/g}$ ${\displaystyle f=d/g}$ ${\displaystyle s=r/g^{2}}$ ${\displaystyle e^{2}+f^{2}=qs}$ ${\displaystyle e}$ ${\displaystyle f}$ ${\displaystyle s<q/2}$

${\displaystyle qs=e^{2}+f^{2}\leq c^{2}+d^{2}<\left({\frac {q}{2}}\right)^{2}+\left({\frac {q}{2}}\right)^{2}=q^{2}/2.}$

Теперь, наконец, шаг спуска : если не является суммой двух квадратов, то по шагу (3.) должен быть множитель, скажем, который не является суммой двух квадратов. Но и, таким образом, повторяя эти шаги (сначала с вместо , и так далее до бесконечности ), мы сможем найти строго убывающую бесконечную последовательность положительных целых чисел, которые сами по себе не являются суммами двух квадратов, но которые делятся на сумму двух взаимно простых квадратов. Поскольку такой бесконечный спуск невозможен, мы заключаем, что должно быть выражено как сумма двух квадратов, как и утверждается. ${\displaystyle q}$ ${\displaystyle q_{1}}$ ${\displaystyle s}$ ${\displaystyle q_{1}\leq s<q/2<q}$ ${\displaystyle e,f;q_{1}}$ ${\displaystyle a,b;q}$ ${\displaystyle q,q_{1},q_{2},\ldots }$ ${\displaystyle q}$

5. Каждое простое число формы является суммой двух квадратов. ${\displaystyle 4n+1}$ (Это основной результат второй работы Эйлера).

Если , то по Малой теореме Ферма каждое из чисел сравнимо с единицей по модулю . Следовательно, все разности делятся на . Каждая из этих разностей может быть разложена на множители как ${\displaystyle p=4n+1}$ ${\displaystyle 1,2^{4n},3^{4n},\dots ,(4n)^{4n}}$ ${\displaystyle p}$ ${\displaystyle 2^{4n}-1,3^{4n}-2^{4n},\dots ,(4n)^{4n}-(4n-1)^{4n}}$ ${\displaystyle p}$

${\displaystyle a^{4n}-b^{4n}=\left(a^{2n}+b^{2n}\right)\left(a^{2n}-b^{2n}\right).}$

Так как является простым числом, оно должно делить один из двух множителей. Если в любом из случаев оно делит первый множитель, то по предыдущему шагу мы заключаем, что само является суммой двух квадратов (так как и отличаются на , они взаимно просты). Поэтому достаточно показать, что не всегда может делить второй множитель. Если оно делит все разности , то оно разделило бы все разности последовательных членов, все разности разностей и так далее. Поскольку все разности th последовательности равны ( Конечная разность ), все разности th были бы постоянными и равными , что, безусловно, не делится на . Следовательно, не может делить все вторые множители, что доказывает, что действительно является суммой двух квадратов. ${\displaystyle p}$ ${\displaystyle 4n-1}$ ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle 1}$ ${\displaystyle p}$ ${\displaystyle 4n-1}$ ${\displaystyle 2^{2n}-1,3^{2n}-2^{2n},\dots ,(4n)^{2n}-(4n-1)^{2n}}$ ${\displaystyle 4n-2}$ ${\displaystyle 4n-3}$ ${\displaystyle k}$ ${\displaystyle 1^{k},2^{k},3^{k},\dots }$ ${\displaystyle k!}$ ${\displaystyle 2n}$ ${\displaystyle (2n)!}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$

Доказательство Лагранжа через квадратичные формы

Лагранж завершил доказательство в 1775 году ^[14], основанное на его общей теории целочисленных квадратичных форм . Следующее изложение включает небольшое упрощение его аргумента, принадлежащее Гауссу , которое появляется в статье 182 Disquisitiones Arithmeticae .

(Целостная бинарная) квадратичная форма — это выражение формы с целыми числами. Говорят, что число представлено формой , если существуют целые числа, такие что . Теорема Ферма о суммах двух квадратов тогда эквивалентна утверждению, что простое число представлено формой (т. е. , ) в точности тогда, когда сравнимо по модулю . ${\displaystyle ax^{2}+bxy+cy^{2}}$ ${\displaystyle a,b,c}$ ${\displaystyle n}$ ${\displaystyle x,y}$ ${\displaystyle n=ax^{2}+bxy+cy^{2}}$ ${\displaystyle p}$ ${\displaystyle x^{2}+y^{2}}$ ${\displaystyle a=c=1}$ ${\displaystyle b=0}$ ${\displaystyle p}$ ${\displaystyle 1}$ ${\displaystyle 4}$

Дискриминант квадратичной формы определяется как . Тогда дискриминант равен . ${\displaystyle b^{2}-4ac}$ ${\displaystyle x^{2}+y^{2}}$ ${\displaystyle -4}$

Две формы и эквивалентны тогда и только тогда , когда существуют подстановки с целыми коэффициентами ${\displaystyle ax^{2}+bxy+cy^{2}}$ ${\displaystyle a'x'^{2}+b'x'y'+c'y'^{2}}$

${\displaystyle x=\alpha x'+\beta y'}$

${\displaystyle y=\gamma x'+\delta y'}$

с таким, что при подстановке в первую форму дают вторую. Легко видеть, что эквивалентные формы имеют тот же дискриминант, а значит, и ту же четность для среднего коэффициента , которая совпадает с четностью дискриминанта. Более того, ясно, что эквивалентные формы будут представлять в точности те же целые числа, поскольку эти виды подстановок могут быть обращены подстановками того же вида. ${\displaystyle \alpha \delta -\beta \gamma =\pm 1}$ ${\displaystyle b}$

Лагранж доказал, что все положительно определенные формы дискриминанта −4 эквивалентны. Таким образом, для доказательства теоремы Ферма достаточно найти любую положительно определенную форму дискриминанта −4, которая представляет . Например, можно использовать форму ${\displaystyle p}$

${\displaystyle px^{2}+2mxy+\left({\frac {m^{2}+1}{p}}\right)y^{2},}$

где первый коэффициент a  =  был выбран так, чтобы форма представляла собой, установив x  = 1 и y  = 0, коэффициент b  = 2 m является произвольным четным числом (каким оно и должно быть, чтобы получить четный дискриминант), и, наконец, выбирается так, чтобы дискриминант был равен −4, что гарантирует, что форма действительно эквивалентна . Конечно, коэффициент должен быть целым числом, поэтому задача сводится к нахождению некоторого целого числа m, такого, чтобы делилось : или, другими словами, «квадратного корня из -1 по модулю » . ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle c={\frac {m^{2}+1}{p}}}$ ${\displaystyle b^{2}-4ac=4m^{2}-4pc}$ ${\displaystyle x^{2}+y^{2}}$ ${\displaystyle c={\frac {m^{2}+1}{p}}}$ ${\displaystyle p}$ ${\displaystyle m^{2}+1}$ ${\displaystyle p}$

Мы утверждаем, что такой квадратный корень из задается выражением . Во-первых, из основной теоремы арифметики Евклида следует , что . Следовательно, : то есть, являются своими собственными обратными по модулю и это свойство уникально для них. Затем из справедливости евклидова деления целых чисел и того факта, что является простым числом, следует, что для каждого наибольший общий делитель и может быть выражен с помощью алгоритма Евклида, что даст уникальный и отличный обратный элемент по модулю . В частности, поэтому произведение всех ненулевых остатков по модулю равно . Пусть : из только что замеченного, . Но по определению, поскольку каждый член в может быть сопряжен со своим отрицательным членом в , , который, поскольку является нечетным, показывает, что , как и требовалось. ${\displaystyle -1}$ ${\displaystyle K=\prod _{k=1}^{\frac {p-1}{2}}k}$ ${\displaystyle ab\equiv 0{\pmod {p}}\iff a\equiv 0{\pmod {p}}\ \ {\hbox{or}}\ \ b\equiv 0{\pmod {p}}}$ ${\displaystyle a^{2}\equiv 1{\pmod {p}}\iff a\equiv \pm 1{\pmod {p}}}$ ${\displaystyle \pm 1}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle 2\leq a\leq p-2}$ ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle a^{-1}\neq a}$ ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle -1}$ ${\displaystyle L=\prod _{l={\frac {p+1}{2}}}^{p-1}l}$ ${\displaystyle KL\equiv -1{\pmod {p}}}$ ${\displaystyle K}$ ${\displaystyle L}$ ${\displaystyle L=(-1)^{\frac {p-1}{2}}K}$ ${\displaystyle p}$ ${\displaystyle K^{2}\equiv -1{\pmod {p}}\iff p\equiv 1{\pmod {4}}}$

Два доказательства Дедекинда с использованием гауссовых целых чисел

Рихард Дедекинд дал по крайней мере два доказательства теоремы Ферма о суммах двух квадратов, оба используя арифметические свойства гауссовых целых чисел , которые являются числами вида a + bi , где a и b — целые числа, а i — квадратный корень из −1. Одно из них появилось в разделе 27 его изложения идеалов, опубликованного в 1877 году; второе появилось в Дополнении XI к работе Петера Густава Лежена Дирихле « Vorlesungen über Zahlentheorie » и было опубликовано в 1894 году.

1. Первое доказательство. Если p — нечетное простое число , то в гауссовых целых числах имеем . Следовательно, записывая гауссовское целое число ω = x + iy с x,y ∈ Z и применяя автоморфизм Фробениуса в Z [ i ]/( p ), находим ${\displaystyle i^{p-1}=(-1)^{\frac {p-1}{2}}}$

${\displaystyle \omega ^{p}=(x+yi)^{p}\equiv x^{p}+y^{p}i^{p}\equiv x+(-1)^{\frac {p-1}{2}}yi{\pmod {p}},}$

поскольку автоморфизм фиксирует элементы Z /( p ). В текущем случае для некоторого целого числа n, и поэтому в приведенном выше выражении для ω ^p , показатель ⁠ ⁠ степени −1 четный. Следовательно, правая часть равна ω, поэтому в этом случае эндоморфизм Фробениуса Z [ i ]/( p ) является тождеством. ${\displaystyle p=4n+1}$ ${\displaystyle (p-1)/2}$

Куммер уже установил, что если f ∈ {1,2} — порядок автоморфизма Фробениуса Z [ i ]/( p ), то идеал в Z [ i ] будет произведением 2/ f различных простых идеалов . (На самом деле, Куммер установил гораздо более общий результат для любого расширения Z , полученного присоединением примитивного корня степени m из единицы , где m — любое положительное целое число; это случай m = 4 этого результата.) Следовательно, идеал ( p ) является произведением двух различных простых идеалов в Z [ i ]. Поскольку гауссовы целые числа являются евклидовой областью для функции нормы , каждый идеал является главным и порождается ненулевым элементом идеала минимальной нормы. Поскольку норма мультипликативна, норма генератора одного из идеальных множителей ( p ) должна быть строгим делителем , так что мы должны иметь , что дает теорему Ферма. ${\displaystyle (p)}$ ${\displaystyle N(x+iy)=x^{2}+y^{2}}$ ${\displaystyle \alpha }$ ${\displaystyle N(p)=p^{2}}$ ${\displaystyle p=N(\alpha )=N(a+bi)=a^{2}+b^{2}}$

2. Второе доказательство. Это доказательство строится на результате Лагранжа, что если — простое число, то должно быть целое число m , делящееся на p (мы также можем увидеть это с помощью критерия Эйлера ); оно также использует тот факт, что гауссовы целые числа являются уникальной областью факторизации (потому что они являются евклидовой областью). Поскольку p ∈ Z не делит ни одно из гауссовских целых чисел и (поскольку оно не делит их мнимые части ), но делит их произведение , следует, что p не может быть простым элементом в гауссовских целых числах. Поэтому мы должны иметь нетривиальную факторизацию p в гауссовских целых числах, которая ввиду нормы может иметь только два множителя (поскольку норма мультипликативна, и , может быть только до двух множителей p), поэтому она должна иметь вид для некоторых целых чисел x и y . Это немедленно дает, что . ${\displaystyle p=4n+1}$ ${\displaystyle m^{2}+1}$ ${\displaystyle m+i}$ ${\displaystyle m-i}$ ${\displaystyle m^{2}+1}$ ${\displaystyle p^{2}=N(p)}$ ${\displaystyle p=(x+yi)(x-yi)}$ ${\displaystyle p=x^{2}+y^{2}}$

Доказательство по теореме Минковского

Для конгруэнтности mod простому числу, является квадратичным вычетом mod по критерию Эйлера . Следовательно, существует целое число, такое что делит . Пусть будут стандартными базисными элементами для векторного пространства и заданы и . Рассмотрим решетку . Если то . Таким образом, делит для любого . ${\displaystyle p}$ ${\displaystyle 1}$ ${\displaystyle 4}$ ${\displaystyle -1}$ ${\displaystyle p}$ ${\displaystyle m}$ ${\displaystyle p}$ ${\displaystyle m^{2}+1}$ ${\displaystyle {\hat {i}},{\hat {j}}}$ ${\displaystyle \mathbb {R} ^{2}}$ ${\displaystyle {\vec {u}}={\hat {i}}+m{\hat {j}}}$ ${\displaystyle {\vec {v}}=0{\hat {i}}+p{\hat {j}}}$ ${\displaystyle S=\{a{\vec {u}}+b{\vec {v}}\mid a,b\in \mathbb {Z} \}}$ ${\displaystyle {\vec {w}}=a{\vec {u}}+b{\vec {v}}=a{\hat {i}}+(am+bp){\hat {j}}\in S}$ ${\displaystyle \|{\vec {w}}\|^{2}\equiv a^{2}+(am+bp)^{2}\equiv a^{2}(1+m^{2})\equiv 0{\pmod {p}}}$ ${\displaystyle p}$ ${\displaystyle \|{\vec {w}}\|^{2}}$ ${\displaystyle {\vec {w}}\in S}$

Площадь фундаментального параллелограмма решетки равна . Площадь открытого диска радиуса с центром в начале координат равна . Кроме того, является выпуклым и симметричным относительно начала координат. Следовательно, по теореме Минковского существует ненулевой вектор такой, что . Оба и поэтому . Следовательно, является суммой квадратов компонент . ${\displaystyle p}$ ${\displaystyle D}$ ${\displaystyle {\sqrt {2p}}}$ ${\displaystyle 2\pi p>4p}$ ${\displaystyle D}$ ${\displaystyle {\vec {w}}\in S}$ ${\displaystyle {\vec {w}}\in D}$ ${\displaystyle \|{\vec {w}}\|^{2}<2p}$ ${\displaystyle p\mid \|{\vec {w}}\|^{2}}$ ${\displaystyle p=\|{\vec {w}}\|^{2}}$ ${\displaystyle p}$ ${\displaystyle {\vec {w}}}$

«Доказательство одним предложением» Загира

Пусть будет простым, обозначим натуральные числа (с нулем или без него) и рассмотрим конечное множество троек чисел. Тогда имеет две инволюции : очевидную, неподвижные точки которой соответствуют представлениям в виде суммы двух квадратов, и более сложную, ${\displaystyle p=4k+1}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle S=\{(x,y,z)\in \mathbb {N} ^{3}:x^{2}+4yz=p\}}$ ${\displaystyle S}$ ${\displaystyle (x,y,z)\mapsto (x,z,y)}$ ${\displaystyle (x,y,y)}$ ${\displaystyle p}$

${\displaystyle (x,y,z)\mapsto {\begin{cases}(x+2z,~z,~y-x-z),\quad {\textrm {if}}\,\,\,x<y-z\\(2y-x,~y,~x-y+z),\quad {\textrm {if}}\,\,\,y-z<x<2y\\(x-2y,~x-y+z,~y),\quad {\textrm {if}}\,\,\,x>2y\end{cases}}}$

которая имеет ровно одну неподвижную точку . Это доказывает, что мощность нечетна. Следовательно, имеет также неподвижную точку относительно очевидной инволюции. ${\displaystyle (1,1,k)}$ ${\displaystyle S}$ ${\displaystyle S}$

Это доказательство, предложенное Загиером , является упрощением более раннего доказательства Хит-Брауна , которое, в свою очередь, было вдохновлено доказательством Лиувилля . Техника доказательства представляет собой комбинаторный аналог топологического принципа, согласно которому эйлеровы характеристики топологического пространства с инволюцией и его множества неподвижных точек имеют одинаковую четность, и напоминает использование инволюций, меняющих знак, в доказательствах комбинаторных биекций.

Это доказательство эквивалентно геометрическому или «визуальному» доказательству с использованием фигур «ветряная мельница», данному Александром Спиваком в 2006 году и описанному в этой публикации на MathOverflow Морицем Фиршингом и в этом видео на YouTube Mathologer .

Доказательство с помощью теории разбиения

В 2016 году А. Дэвид Кристофер дал доказательство на основе теории разбиений, рассмотрев разбиения нечетного простого числа , имеющие ровно два размера , каждое из которых встречается ровно раз, и показав, что по крайней мере одно такое разбиение существует, если оно сравнимо с 1 по модулю 4. ^[15] ${\displaystyle n}$ ${\displaystyle a_{i}(i=1,2)}$ ${\displaystyle a_{i}}$ ${\displaystyle n}$

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

• Теорема Лежандра о трех квадратах
• Теорема Лагранжа о четырех квадратах
• Константа Ландау–Рамануджана
• Лемма Туэ
• Теорема Фридлендера–Иванца

Ссылки

• DA Cox (1989). Простые числа вида x ²  + ny ² . Wiley-Interscience. ISBN 0-471-50654-0.*Ричард Дедекинд, Теория целых алгебраических чисел .
• LE Dickson . История теории чисел, т. 2. Chelsea Publishing Co., Нью-Йорк, 1920 г.
• Гарольд М. Эдвардс , Великая теорема Ферма. Генетическое введение в алгебраическую теорию чисел . Graduate Texts in Mathematics № 50, Springer-Verlag, Нью-Йорк, 1977.
• CF Gauss, Disquisitiones Arithmeticae (английское издание). Перевод Артура А. Кларка. Springer-Verlag, 1986.
• Голдман, Джей Р. (1998), Королева математики: исторически мотивированное руководство по теории чисел , AK Peters , ISBN 1-56881-006-7
• DR Heath-Brown, Теорема Ферма о двух квадратах . Invariant, 11 (1984) стр. 3–5.
• Джон Стиллвелл , Введение в теорию целых алгебраических чисел Ричарда Дедекинда. Кембриджская математическая библиотека, Cambridge University Press, 1996. ISBN 0-521-56518-9 
• Дон Загир , Однопредложение доказательства того, что каждое простое число p ≡ 1 mod 4 является суммой двух квадратов . Amer. Math. Monthly 97 (1990), № 2, 144, doi :10.2307/2323918

Примечания

1. Для доказательства обратного см., например, 20.1, теоремы 367 и 368 в: GH Hardy и EM Wright. Введение в теорию чисел, Оксфорд, 1938.
2. Саймон Стевин . «Арифметика Симона Стевена де Брюгге», с аннотациями Альберта Жирара, Лейд, 1625, стр. 622.
3. LE Dickson, History of the Theory of Numbers, Vol. II, Ch. VI, p. 227. "A. Girard ... уже дал определение чисел, выражаемых как сумма двух целых квадратов: каждый квадрат, каждое простое число 4n+1, произведение, образованное из таких чисел, и удвоенное число предыдущего"
4. LE Dickson, История теории чисел, т. II, гл. VI, стр. 228.
5. Вагон, Стэн (1990), «Уголок редактора: Евклидов алгоритм снова наносит удар», American Mathematical Monthly , 97 (2): 125, doi : 10.2307/2323912, MR  1041889.
6. De numeris qui sunt aggregata duorum Quadatorum. (Novi commentarii academiae scientiarum Petropolitanae 4 (1752/3), 1758, 3–40)
7. Демонстрация теоремы ФЕРМАТИАНИ omnem numerum primum formae 4n+1 esse summam duorumquadatorum. (Novi commentarii academiae scientiarum Petropolitanae 5 (1754/5), 1760, 3–13)
8. Загир, Д. (1990), «Доказательство одним предложением того, что каждое простое число p  ≡ 1 (mod 4) является суммой двух квадратов», American Mathematical Monthly , 97 (2): 144, doi :10.2307/2323918, MR  1041893.
9. А. Дэвид Кристофер. «Теоретико-раздельное доказательство теоремы Ферма о двух квадратах», Discrete Mathematics 339 :4:1410–1411 (6 апреля 2016 г.) doi :10.1016/j.disc.2015.12.002
10. Эйлер а Гольдбах, письмо CXXV
11. De numeris qui sunt aggregata duorum Quadatorum. (Novi commentarii academiae scientiarum Petropolitanae 4 (1752/3), 1758, 3–40) [1]
12. Демонстрация теоремы ФЕРМАТИАНИ omnem numerum primum formae 4n+1 esse summam duorumquadatorum. (Novi commentarii academiae scientiarum Petropolitanae 5 (1754/5), 1760, 3–13) [2]
13. Краткое изложение основано на книге Эдвардса, страницы 45–48.
14. Ноув. Память акад. Берлин, 1771 год, 125; там же. Анна 1773, 275; там же, 1775 г., 351.
15. А. Дэвид Кристофер, Теоретико-раздельное доказательство теоремы Ферма о двух квадратах", Дискретная математика, 339 (2016) 1410–1411.

Внешние ссылки

• Еще два доказательства на PlanetMath.org
• «Доказательство теоремы одним предложением». Архивировано из оригинала 5 февраля 2012 года.{{cite web}}: CS1 maint: unfit URL (link)
• Теорема Ферма о двух квадратах, Д.Р. Хит-Браун, 1984.
• Польстер, Буркард (2019) «Теорема Рождества Ферма: визуализация скрытого круга в π/4 = 1 – 1/3 + 1/5 – 1/7 + ...» (Видео). Матолог .