Квадратни закон реципроцитета

Квадратни закон реципроцитета, понекад називан и Гаусов закон реципроцитета, основни је закон из теорије бројева, потпоља математике. Бави се питањем да ли за непаран прост број $p$ и цео број, који није дељив са њим, $a$ постоји квадратни број $m^2$, тако да је разлика $m^2-a$ дељива са $p$. Тачније, заједно са два допунска става наведена у наставку, даје поступак за одлучивање да ли је број квадратни остатак или неостатак простог броја. Откриће квадратног закона реципроцитета од стране Леонарда Ојлера и доказ од стране Гауса (Disquisitiones Arithmeticae 1801, иако је доказ имао већ 1796) били су полазне тачке за развој модерне алгебарске теорије бројева.

Да би се разумела тачна изјава квадратног закона реципроцитета, потребни су само концепти квадратних бројева, простих бројева и дељивости целих бројева са остатком. Његова формулација почиње избором два непарна, неједнака проста броја $p$ и $q$, на пример $p=5$ и $q=19$. У центру је следеће питање:

Да ли постоји квадратни број $m^2$, тако да $p$ дели разлику $m^2-q$? (Са горњим примерима: Да ли је број $m^2-19$ за неки квадратни број $m^2$ дељив са $5$?).

Унутар овог питања, два проста броја $p$ и $q$ имају различите улоге ($p$ је „делилац“, а $q$ је „суптрахенд“). Реч „реципроцитет“ (од „реципрочан“, дакле узајаман) сада указује на то да се исто питање може поставити и са замењеним улогама оба проста броја: Да ли, дакле, постоји (други) квадратни број $n^2$, тако да $q$ опет дели разлику $n^2-p$? Квадратни закон реципроцитета формулише једноставно правило које повезује решивост ова два задатка, која настају заменом улога оба проста броја. Разликује се:

• Ако барем један од два проста броја $p$ и $q$ при дељењу са $4$ даје остатак $1$, онда је једно питање тачно тада одговориво са „Да“, када је и друго. На пример, $p=5$ при дељењу са $4$ даје остатак $1$. Са изборима $q=19$, $m^2=2^2=4$ и $n^2=9^2=81$ добија се $4-19=-15$ и $81-5=76$, при чему је први дељив са $5$, а други са $19$ (пошто је $76=4\cdot 19$). Дакле, у случају $p=5$ и $q=19$, питање се може узајамно одговорити са „Да“, како предвиђа закон реципроцитета. Насупрот томе, не постоје квадратни бројеви $m^2$ и $n^2$, тако да је $m^2-3$ дељив са $5$, а $n^2-5$ дељив са $3$.
• Ако, међутим, оба проста броја $p$ и $q$ при дељењу са $4$ дају остатак $3$, онда је увек тачно једно од питања одговориво са „Да“. Пример $p=3$ и $q=7$: $1^2-7=-6$ је дељив са $3$, али не постоји квадратни број $n^2$ тако да је $n^2-3$ дељив са $7$. И $3$ и $7$ при дељењу са $4$ дају остатак $3$.

У терминима Лежандровог симбола, овај однос за непарне просте бројеве $p≠q$ изражава се као

$\left(\frac{p}{q}\right)=(-1{)}^{\frac{p-1}{2}\frac{q-1}{2}}\left(\frac{q}{p}\right).$

Квадратни закон реципроцитета је из математичке перспективе занимљив, између осталог, јер успоставља везу између наизглед различитих питања. То доводи до тога да се решење једног понекад врло тешког задатка може свести на решавање лаког задатка, због чега је користан за конкретне прорачуне. Бројне примене налази у теорији бројева, теорији диофантских једначина, али и у практичним областима попут криптографије.

Сам Гаус је представио осам методички различитих доказа за квадратни закон реципроцитета. Пошто је значај резултата већ препознао као изузетно висок, свој резултат је назвао „фундаменталном теоремом“ односно „Theorema aureum“ (српски: „Златни став“). Назив „закон реципроцитета“ потиче од Адријена-Мари Лежандра, који је 1785. године дао непотпун доказ. Каснији (потпуни) докази потичу, између осталих, од Готхолда Ајзенштајна, Петера Густава Лежена Дирихлеа, Рихарда Дедекинда и Јегора Ивановича Золотарјова. До данас је објављено више од 300 различитих доказа. Упркос елементарним доказима, суштина „реципроцитета“, како је Гаус већ претпостављао, лежи релативно дубоко, наиме у растављању на просте чиниоце у циклотомичним пољима.

Квадратни закон реципроцитета даје изјаве о решивости квадратних једначина у модуларној аритметици. Питање решивости једначина вишег степена води ка вишим законима реципроцитета, што је била једна од покретачких снага алгебарске теорије бројева од Гауса. Случај трећег степена, кубни закон реципроцитета, обрадио је Готхолд Ајзенштајн, случај четвртог степена Гаус, при чему је, међутим, Карл Густав Јакоби дао први потпуни доказ. Модерна, много дубља генерализација налази се у основама теорије поља класа.

Питање и основе

Квадратни закон реципроцитета мотивисан је задатком брзог одлучивања о решивости квадратних конгруенција. У случају простих бројева, ово одговара квадратној једначини над коначним пољем. За тачно разумевање његове изјаве, сажете су следеће основе.

Коначна поља

Шаблон:Главни У математици, поље означава скуп унутар којег се, једноставно речено, може рачунати са четири основне рачунске операције. Притом треба да важе правила позната из школске математике о комутативности (заменљивост код „плус“ и „пута“), асоцијативности (заменљивост заграда код „само плус“ или „само пута“) и дистрибутивности („извлачење заграде“ и „множење заграде“). Осим тога, елементи $0$ (неутрални елемент сабирања) и $1$ (неутрални елемент множења) увек морају бити део поља. Посебно, треба да буде могуће делити сваким бројем различитим од $0$. Важни примери су поље реалних бројева (ознака: $ℝ$) или поље рационалних бројева (ознака: $\mathbb{Q}$).

Важан захтев је да ниједна од дозвољених рачунских операција не доводи до напуштања скупа бројева који дефинише поље. Тако, на пример, у пољима генерално није дозвољено вадити квадратни корен. Број $2$ је елемент од $\mathbb{Q}$, кратко $2\in \mathbb{Q}$, али $\sqrt{2}$ је ирационалан број, дакле $\sqrt{2}\notin \mathbb{Q}$. Слично, $-1$ нема квадратни корен у реалним бројевима. У основи, концепт квадратног корена у пољу је индиректно дефинисан, јер је обрнута операција, наиме множење броја са самим собом, дефинисана у пољима, при чему је постојање друго питање.

Питање из алгебре је како поља могу изгледати, односно у којим типовима скупова је могуће „затворено рачунање“. Тако се могу додати други нерационални бројеви у $\mathbb{Q}$ како би се конструисала већа поља. Пример је поље $\mathbb{Q}(\sqrt{2})$, које се састоји од свих бројева облика $x+\sqrt{2}y$ са $x,y\in \mathbb{Q}$ (види такође: поље бројева, и на пример квадратно поље бројева). Рачунице као

$(-2+3\sqrt{2})+(3-\sqrt{2})=1+2\sqrt{2},(1-\sqrt{2})\cdot (2+\frac{3}{7}\sqrt{2})=\frac{8}{7}-\frac{11}{7}\sqrt{2},\frac{3+\sqrt{2}}{4-2\sqrt{2}}=2+\frac{5}{4}\sqrt{2}$

су прототипови затворености четири основне рачунске операције у $\mathbb{Q}(\sqrt{2})$. $\mathbb{Q}(\sqrt{2})$, заједно са $\mathbb{Q}$ и $ℝ$, је још један пример поља са бесконачно много елемената. Значајно је, међутим, да постоје и поља $𝕂$ са само коначно много елемената. Рачунање у овим областима, иако су закони на крају исти, одступа од „класичне интуиције“. То почиње тиме што елементи

$1=1,1+1=2,1+1+1=3,1+1+1+1=4,\cdots$

не могу сви бити различити, јер $𝕂$ има само коначно много елемената. Пошто се увек има $0≠1$ (иначе би било $𝕂=\{0\}$, а тај тривијални случај се искључује), постоји најмањи природни број $p>1$, такав да

$\underset{p\text{-пута}}{\underbrace{1+1+\cdots +1}}=0$

у $𝕂$ први пут буде испуњено. Овај показатељ се назива карактеристика поља $𝕂$, дакле $\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{r}(𝕂)=p$. Она је увек прост број, јер ако би на пример било $\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{r}(𝕂)=2\cdot 3$ сложено, онда би морало бити $2\cdot 3=0$, и већ би било $2=1+1=0$ или $3=1+1+1=0$, дакле $\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{r}(𝕂)\le 3$, што би директно противречило претпоставци $\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{r}(𝕂)=6$ због минималности карактеристике. Да би се тачно разумело рачунање у коначним пољима, неопходно је баратање са остацима при дељењу. Нетривијални остаци настају код дељења која се не завршавају без остатка. На пример, $19$ подељено са $5$ је $3$ са остатком $4$. У најједноставнијим примерима коначних поља, рачуна се управо са тим остацима. Ово се може демонстрирати на примеру: Постоји тачно пет могућих остатака при дељењу са $5$, и они одговарају

$\{\bar{0},\bar{1},\bar{2},\bar{3},\bar{4}\}=\{0+5\mathbb{Z},1+5\mathbb{Z},2+5\mathbb{Z},3+5\mathbb{Z},4+5\mathbb{Z}\}$

са $\mathbb{Z}=$ скуп целих бројева, и $5\mathbb{Z}=\{\dots ,-10,-5,0,5,10,\dots \}$ (тј. сви цели вишекратници броја $5$). Притом, надвлаке значе да се сви бројеви који при дељењу са $5$ дају одговарајући остатак посматрају заједно или груписано. На пример,

$\bar{4}:=4+5\mathbb{Z}=\{\dots ,-6,-1,4,9,14,19,\dots \}$

састоји се тачно од оних бројева који при дељењу са $5$ имају остатак $4$. Бројеви од $0$ до $4$ су даље само репрезентанти целе класе остатака, на пример, важе једнакости

$\cdots =\overline{-6}=\overline{-1}=\bar{4}=\bar{9}=\overline{14}=\overline{19}=\cdots .$

Одговарајући репрезентанти дају при дељењу са $5$ сви исти остатак $4$ и тако припадају истој класи остатака. Тиме се види да адитивни вишекратници од $5$ у овом примеру за припадност истој класи остатака увек не играју улогу. Другим речима: док је цео број увек потпуно одређен својом величином, класе остатака су редуковани бројеви. Само је остатак одлучујући, а не више величина.

Са класама остатака модуло $5$ сада се може рачунати са четири основне рачунске операције. Притом важе у основи иста правила као код рачунања у целим бројевима $\mathbb{Z}$: На пример,

$\bar{4}+\bar{4}=\bar{8}=\bar{3}$ (Значење: Збир два било која броја са остатком $4$ при дељењу са $5$ увек има остатак $3$ при дељењу са $5$, на пример $14+34=48$ или $29+4=33$.)

$\bar{4}-\overline{39}=\overline{-35}=\bar{0}$ (Значење: Разлика два било која броја са истим остатком, на пример $4$, при дељењу са $5$, је увек дељива са $5$, дакле има остатак $0$.)

$\bar{2}\cdot \bar{3}=\bar{6}=\bar{1}$ (Значење: Производ два било која броја са остатком $2$ односно $3$ при дељењу са $5$ увек има остатак $1$ при дељењу са $5$, на пример $12\cdot 13=156$ или $2\cdot 33=66.$)

Важно је на овом месту показати да је ово добро дефинисано, дакле да се при избору других репрезената увек добија исти резултат. Пошто је разлика два репрезентанта увек дељива са $5$, то је очигледно: На пример, (упореди горњи пример)

$\overline{14}+\overline{34}=\overline{48}=\bar{3}$

али и

$\overline{29}+\bar{4}=\overline{33}=\bar{3}.$

Сасвим слична разматрања важе и за добро дефинисаност множења. И дељење је унутар $\{\bar{0},\bar{1},\bar{2},\bar{3},\bar{4}\}$ могуће (ако се $\bar{0}$ искључи), јер да би се уопштено могло делити, за свако $a$ је потребна само егзистенција инверза $b$ са

$ab=1$

(као на пример $3$ и $\frac{1}{3}$ у случају рационалних бројева). За доказ да увек постоји инверз, одлучујуће је да је $5$ прост број: Ако прост број дели производ $mn$ два цела броја, онда већ мора делити барем један од фактора. Када се ово има, аргументација је следећа: За елемент $\bar{a}\in \{\bar{1},\bar{2},\bar{3},\bar{4}\}$, који се жели инвертовати, посматрају се сви могући вишекратници (различити од нуле):

$\bar{1}\cdot \bar{a},\bar{2}\cdot \bar{a},\bar{3}\cdot \bar{a},\bar{4}\cdot \bar{a}.$

Класа остатака $\bar{0}$ се не појављује у овој листи, јер ниједан од бројева $1a,2a,3a,4a$ није дељив са $5$. Даље, сви уноси у листи су парно различити, јер је $\bar{m}\cdot \bar{a}=\bar{n}\cdot \bar{a}$ еквивалентно томе да је $(\bar{m}-\bar{n})\cdot \bar{a}=\bar{0}$, дакле $5|(m-n)a$. Пошто $a$ није дељив са $5$, $m-n$ мора бити дељив са $5$. Разлика $m-n$ лежи, према избору горњих репрезената $1\le m,n\le 4$, у интервалу $-3\le m-n\le 3$, а само је $0$ ту дељив са $5$. Дакле, $m=n$. Мора се дакле класа остатака $\bar{1}$ појавити негде у горњој листи и инверз је пронађен. На пример, $\bar{2}$ је инверз од $\bar{3}$ модуло $5$, јер је $\bar{2}\cdot \bar{3}=\bar{6}=\bar{1}$. Пошто се у суштини „и даље рачуна у целим бројевима“, остају очувани комутативни закон, асоцијативни закон и дистрибутивни закон, чиме скуп класа остатака ${𝔽}_5:=\{\bar{0},\bar{1},\bar{2},\bar{3},\bar{4}\}$ заиста формира поље.

Цела ова аргументација се не ограничава на прост број $5$, већ се за сваки прост број $p$ може навести одговарајуће коначно поље:

${𝔽}_2=\{\bar{0},\bar{1}\},{𝔽}_3=\{\bar{0},\bar{1},\bar{2}\},{𝔽}_5=\{\bar{0},\bar{1},\bar{2},\bar{3},\bar{4}\},{𝔽}_7=\{\bar{0},\bar{1},\bar{2},\bar{3},\bar{4},\bar{5},\bar{6}\},{𝔽}_{11}=\{\bar{0},\bar{1},\bar{2},\bar{3},\bar{4},\bar{5},\bar{6},\bar{7},\bar{8},\bar{9},\overline{10}\},\dots$

итд. Притом, класе остатака означене надвлакама морају се, наравно, увек примењивати на дотични прост број.

Модуларна аритметика

Шаблон:Главни Модуларна аритметика у суштини означава рачунање са класама остатака и с тим повезане области, као што су једначине. За природни број $N$, „модул“, два цела броја $a$ и $b$ се називају конгруентним модуло $N$, ако $N$ дели њихову разлику, дакле у ознакама

$N|(a-b).$

У овом случају, конгруенција се пише и као

$a\equiv b(\mathrm{mod}N),$

читано као: „$a$ конгруентно $b$ модуло $N$“. На пример, важи

$3\equiv 8(\mathrm{mod}5),$

јер $5$ дели разлику $3-8=-5$. Ако су два цела броја конгруентна модуло $N$, припадају истој класи остатака при дељењу са $N$ (и обрнуто). Тада се пише $\bar{a}=\bar{b}$, и са класама остатака се може рачунати као и обично (види претходни одељак о коначним пољима). Ако је $N$ прост број, скуп класа остатака модуло $N$ формира поље ${𝔽}_N$. Ако је $N>1$, међутим, сложен, ради се само о комутативном прстену. Комутативни прстенови су по својим својствима слични пољима (алгебарске структуре са сабирањем и множењем), међутим, дељење није увек могуће. Пример је $\mathbb{Z}/4\mathbb{Z}:=\{\bar{0},\bar{1},\bar{2},\bar{3}\}$, дакле скуп класа остатака модуло $4$ (пошто $4$ није прост број!). Овде није могуће дељење са $\bar{2}$, јер $\bar{2}\cdot \bar{2}=\bar{4}=\bar{0}$. Из „дељења“ обе стране са $\bar{2}$ би следило $\bar{2}=\bar{0}$, што не може бити, јер $2$ није дељив са $4$. Елементи прстена којима се ипак може делити (у то увек спада јединица) називају се јединицама (прстена). Јединице прстена целих бројева $\mathbb{Z}$ су $\{\pm 1\}$, а прстена $\mathbb{Z}/4\mathbb{Z}$ су $\{\bar{1},\bar{3}\}$ (као што је виђено, поред $\bar{0}$, и $\bar{2}$ модуло $4$ није јединица, јер се ни са једним од та два елемента не може делити).

Квадратне једначине

Квадратна једначина је једначина облика

$Q:a{x}^2+bx+c=0,(a≠0)$

са једном непознатом $x$. Ради се дакле о специјалном случају алгебарске једначине, где се непозната $x$ једноставно може помножити сама са собом. У основи, алгебарске једначине, које се састоје од примене четири основне рачунске операције, могу се проучавати над пољима, где све те рачунске операције имају смисла. У школској математици, на пример, као основа се узима поље $ℝ$. Дакле, $a,b,c\in ℝ$, и занимају нас решења $x$ једначине $a{x}^2+bx+c=0$ у реалним бројевима. Међутим, горња једначина, ако је $a,b,c\in \mathbb{Q}$, може се посматрати и само над рационалним бројевима. На пример, једначина $x^2-2=0$ над реалним бројевима има решења $x=\pm \sqrt{2}$, али над рационалним бројевима нема решење. У алгебри и теорији бројева, првенствено се занимамо за брз поступак одлучивања да ли алгебарска једначина уопште има решење у свом пољу. Погодно је овде радити са „показатељима“. Горњој квадратној једначини може се доделити број

$D_Q:=b^2-4ac$

који се брзо може израчунати из коефицијената $a,b$ и $c$. Он се такође назива дискриминантом (латински: discriminare = разликовати) једначине $Q$. Преко формула за решавање квадратне једначине, која потенцијална решења идентификује као

$x_{1,2}=\frac{-b\pm \sqrt{b^2-4ac}}{2a}$

, препознаје се да једначина $Q$ има решења у датом пољу тачно онда када има смисла вадити квадратни корен из дискриминанте. Тачније, $Q$ има

Графици три квадратне функције над реалним бројевима:
Зелена има дискриминанту $0$ (једну реалну нулу),
Плава негативну (нема реалних нула) и
Наранџаста позитивну (две реалне нуле) дискриминанту

• тачно две различите нуле, ако је $b^2-4ac≠0$ и квадрат у датом пољу (дакле, израз $\sqrt{b^2-4ac}$ је садржан у пољу и није једнак 0),
• тачно једну („двоструку“) нулу, ако је $b^2-4ac=0$ (јер увек важи $\pm \sqrt{0}=\pm 0=0$, а $0$ је увек део поља),
• тачно нема решења, ако $b^2-4ac$ није квадрат у датом пољу.

У случају поља $ℝ$, дакле, треба разликовати само случајеве $D_Q>0$, $D_Q=0$ и $D_Q<0$, јер реалан број различит од $0$ има квадратни корен у $ℝ$ тачно онда када је позитиван. Код рационалних бројева, међутим, разлика је суптилнија. Као што је већ горе виђено, једначина $x^2-2=0$ нема рационалних решења, и заиста, њена дискриминанта $D=0^2-4\cdot 1\cdot (-2)=8$ јесте позитивна, али није квадрат рационалног броја. Ово је први наговештај да је аритметика у реалним бројевима једноставнија од оне у рационалним бројевима.

Поред реалних или рационалних бројева, квадратне једначине типа

$\bar{a}{x}^2+\bar{b}x+\bar{c}=\bar{0}(\bar{a},\bar{b},\bar{c}\in {𝔽}_p,\bar{a}≠\bar{0})$

могу се проучавати над пољем ${𝔽}_p$ (са $p>2$). Квадратни закон реципроцитета може помоћи да се брзо одлучи да ли постоји решење или не. Притом се случај карактеристике 2 (посебно ${𝔽}_2$) мора посматрати засебно, јер се у формули за решавање квадратне једначине дели са $2a$, дакле у таквим пољима са $0$, што није дозвољено. Зато је теорија квадратних једначина у таквим пољима другачија.

Квадратни остаци и Лежандров симбол

Да би се одлучило да ли је квадратна једначина $a{x}^2+bx+c=0$ са $a,b,c\in {𝔽}_p$ решива над ${𝔽}_p$ са простим бројем $p>2$, довољно је одлучити да ли је дискриминанта $b^2-4ac$ квадрат у ${𝔽}_p$. Случај $p=2$ игра посебну улогу, јер се у формули за решавање квадратне једначине дели са $2a$, што би у случају $p=2$ значило дељење нулом, што није дозвољено. Ово мотивише појам квадратног остатка. Тиме се мисли на оне елементе коначног поља ${𝔽}_p$ који су различити од нуле и настају квадрирањем (другог) елемента из ${𝔽}_p$. Другим речима, број $n$ који је узајамно прост са $p$ је тачно онда квадратни остатак модуло $p$, ако постоји квадратни број $m^2$ тако да је $n-m^2$ дељив са $p$. Из квадратних остатака се у датом пољу може извући квадратни корен, што је од значаја при решавању квадратних једначина. Елементи из ${𝔽}_p$ који нису нула и нису квадратни остаци, називају се и квадратни неостаци. Ако је, на пример, $p=11$, квадрирањем класа остатака $\{\bar{1},\bar{2},\bar{3},\bar{4},\bar{5},\bar{6},\bar{7},\bar{8},\bar{9},\overline{10}\}$ модуло $11$ добија се:

$\overline{1^2}=\bar{1},\overline{2^2}=\bar{4},\overline{3^2}=\bar{9},\overline{4^2}=\overline{16}=\bar{5},\overline{5^2}=\overline{25}=\bar{3},\overline{6^2}=\overline{36}=\bar{3},\overline{7^2}=\overline{49}=\bar{5},\overline{8^2}=\overline{64}=\bar{9},\overline{9^2}=\overline{81}=\bar{4},\overline{10^2}=\overline{100}=\bar{1}.$

Дакле, елементи $\bar{1},\bar{3},\bar{4},\bar{5}$ и $\bar{9}$ су квадратни остаци модуло $11$. Стога, на пример, једначина

$Q_1:x^2+\bar{4}x+\bar{5}=\bar{0}$

није решива у ${𝔽}_{11}$, јер је

$D_{Q_1}={\bar{4}}^2-\bar{4}\cdot \bar{5}=\overline{-4}=\bar{7}$

График квадратне функције $y=x^2-x+\bar{2}$ над коначним пољем ${𝔽}_{11}$. Могу се уочити нуле $x_1=\bar{5}$ и $x_2=\bar{7}$, и важи факторизација $y=(x-\bar{5})(x-\bar{7})$. Увек су бирани репрезентанти у интервалу $[0,10]$.

квадратни неостатак модуло $11$, и последично се у формули за решавање квадратне једначине над ${𝔽}_{11}$ не може извући квадратни корен из дискриминанте. Насупрот томе,

$Q_2:x^2-x+\bar{2}=0$

је решива у ${𝔽}_{11}$, јер је

$D_{Q_2}={\overline{-1}}^2-\bar{4}\cdot \bar{2}=\overline{-7}=\bar{4}$

квадратни остатак модуло $11$. Заиста, на пример, $x=\bar{5}$ је решење, јер је ${\bar{5}}^2-\bar{5}+\bar{2}=\overline{22}=\bar{0}$ модуло $11$.

Занимљиво је да се скуп квадратних остатака и неостатака дели на тачно два једнако велика скупа са бројем елемената $\frac{p-1}{2}$, ако је прост број $p$ непаран. Као што је горе виђено у случају $p=11$, то су скупови $\{\bar{1},\bar{3},\bar{4},\bar{5},\bar{9}\}$ и $\{\bar{2},\bar{6},\bar{7},\bar{8},\overline{10}\}$ са по пет елемената. Уопштено, квадратни остаци модуло $p>2$ могу се, као горе, потпуно одредити посматрањем елемената

$\overline{1^2},\overline{2^2},\overline{3^2},\cdots ,\overline{{\left(\frac{p-1}{2}\right)}^2}$

. Даљи остаци се могу видети у следећој табели, која је потпуна за све просте бројеве до $50$:

Квадрати модуло простих бројева

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
n2	1	4	9	16	25	36	49	64	81	100	121	144	169	196	225	256	289	324	361	400	441	484	529	576	625
mod 3	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1
mod 5	1	4	4	1	0	1	4	4	1	0	1	4	4	1	0	1	4	4	1	0	1	4	4	1	0
mod 7	1	4	2	2	4	1	0	1	4	2	2	4	1	0	1	4	2	2	4	1	0	1	4	2	2
mod 11	1	4	9	5	3	3	5	9	4	1	0	1	4	9	5	3	3	5	9	4	1	0	1	4	9
mod 13	1	4	9	3	12	10	10	12	3	9	4	1	0	1	4	9	3	12	10	10	12	3	9	4	1
mod 17	1	4	9	16	8	2	15	13	13	15	2	8	16	9	4	1	0	1	4	9	16	8	2	15	13
mod 19	1	4	9	16	6	17	11	7	5	5	7	11	17	6	16	9	4	1	0	1	4	9	16	6	17
mod 23	1	4	9	16	2	13	3	18	12	8	6	6	8	12	18	3	13	2	16	9	4	1	0	1	4
mod 29	1	4	9	16	25	7	20	6	23	13	5	28	24	22	22	24	28	5	13	23	6	20	7	25	16
mod 31	1	4	9	16	25	5	18	2	19	7	28	20	14	10	8	8	10	14	20	28	7	19	2	18	5
mod 37	1	4	9	16	25	36	12	27	7	26	10	33	21	11	3	34	30	28	28	30	34	3	11	21	33
mod 41	1	4	9	16	25	36	8	23	40	18	39	21	5	32	20	10	2	37	33	31	31	33	37	2	10
mod 43	1	4	9	16	25	36	6	21	38	14	35	15	40	24	10	41	31	23	17	13	11	11	13	17	23
mod 47	1	4	9	16	25	36	2	17	34	6	27	3	28	8	37	21	7	42	32	24	18	14	12	12	14

Ако се напусти модуларна аритметика и врати се на целе бројеве, онда је $a\in \mathbb{Z}$ тачно онда квадратни остатак модуло простог броја $p$, ако постоји квадратни број $m^2$ тако да је $m^2-a$ дељив са $p$.

Адријен-Мари Лежандр

Са математичке тачке гледишта, корисно је „одвојити“ квадратне остатке од неостатака. Притом се $\bar{0}$ додељује посебна улога. У ту сврху се дефинише Лежандров симбол, назван по Адријен-Мари Лежандру. То је математичка функција ${𝔽}_p\to \{-1,0,1\}$ са доменом ${𝔽}_p$ и кодоменом $\{-1,0,1\}$, која квадратном остатку додељује вредност $1$ („позитивно“), неостатку $-1$ („негативно“) и $\bar{0}$ вредност $0$. У симболима се поставља:

$\left(\frac{\bar{n}}{p}\right):=\left(\frac{n}{p}\right):=\{\begin{array}{cc}1& \text{за }\mathrm{n}\mathrm{z}\mathrm{d}(p,n)=1\text{ и }n\equiv m^{2}modp\text{ за неко }m\in \mathbb{Z},\\ -1& \text{за }\mathrm{n}\mathrm{z}\mathrm{d}(p,n)=1\text{ и }n\equiv ̸m^{2}modp\text{ за свако }m\in \mathbb{Z},\\ 0& \text{за }p|n.\end{array}$

Овде $\mathrm{n}\mathrm{z}\mathrm{d}$ означава највећи заједнички делилац. Израз $(\frac{n}{p})$ се не сме схватити као разломак. У литератури се стога понекад користи и нотација $(n|p)$ да би се избегле забуне. На природан начин, Лежандров симбол се може схватити и као функција на целим бројевима, која је тада, због своје првобитне дефиниције на класама остатака, $p$-периодична. Тада је $(\frac{\bar{n}}{p})=(\frac{n}{p}),$ а последњи израз се најчешће користи.

Важе следећа веома важна правила:

• Производ два квадратна остатка је опет квадратни остатак.
• Производ квадратног остатка и квадратног неостатка је квадратни неостатак.
• Производ два квадратна неостатка је квадратни остатак.

Уместо размишљања у терминима остатака и неостатака, помоћу ових правила се може прећи на $+1$ и $-1$. Аналогно, у овом погледу се поштују правила $1\cdot 1=1$, $1\cdot (-1)=(-1)\cdot 1=-1$ и $(-1)\cdot (-1)=1$. Лежандров симбол служи као „преводилац“ на пример правила „неостатак пута неостатак једнако остатак“ у „негативно пута негативно једнако позитивно“. Посебно следи да је Лежандров симбол потпуно мултипликативан, дакле важи за све $a,b\in \mathbb{Z}$ правило рачунања

$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right).$

Примери

Посматра се пример $p=17$. На пример, $13$ је квадратни остатак модуло $17$, јер је број $8^2-13=64-13=51=3\cdot 17$ дељив са $17$. Краћи облик преко класа остатака гласи $8^2\equiv 13(\mathrm{mod}17)$ или $\overline{8^2}=\overline{13}$. У нотацији Лежандровог симбола то значи $\left(\frac{13}{17}\right)=1.$ Насупрот томе, $5$ је квадратни неостатак модуло $17$. Ни за један квадратни број $m^2$ није $m^2-5$ дељив са $17$. Ово се проверава, на пример, формирањем свих остатака $\overline{1-5},\overline{4-5},\overline{9-5},\mathrm{...},\overline{64-5}$ модуло $17$, при чему никада не испадне $\bar{0}$, дакле дељење са $17$ није могуће. Изражено преко Лежандровог симбола, дакле $\left(\frac{5}{17}\right)=-1.$ Производ остатка и неостатка је сада опет неостатак. $5\cdot 17=85\equiv 14(\mathrm{mod}17)$ (требало би бити $5\cdot 13=65\equiv 14(\mathrm{mod}17)$), па важи $-1=(-1)\cdot 1=\left(\frac{5}{17}\right)\left(\frac{13}{17}\right)=\left(\frac{65}{17}\right)=\left(\frac{14}{17}\right).$ Тиме је $14$ квадратни неостатак модуло $17$. У последњем кораку је коришћено да је Лежандров симбол $\left(\frac{\cdot }{17}\right)$ дефинисан на класама остатака модуло $17$, и тиме је $17$-периодичан.

Изјава квадратног закона реципроцитета

У наставку, $\left(\frac{a}{p}\right)$ са целим бројем $a$ и простим бројем $p$ означава Лежандров симбол. Квадратни закон реципроцитета даје за два различита непарна проста броја $p$ и $q$ једноставну формулу која омогућава међусобно прерачунавање величина $(\frac{p}{q})$ и $(\frac{q}{p})$. Тиме се питање да ли је $p$ квадратни остатак модуло $q$ може брзо одговорити одговарањем на „реципрочно“ питање, да ли је $q$ квадратни остатак модуло $p$. Квадратни закон реципроцитета каже да за два различита непарна проста броја $p$ и $q$ важи:

$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{\frac{p-1}{2}\frac{q-1}{2}}\stackrel{(\ast )}{=}\{\begin{array}{cc}1& p\equiv 1(\mathrm{mod}4)\text{или}q\equiv 1(\mathrm{mod}4),\\ -1& p\equiv 3(\mathrm{mod}4)\text{и}q\equiv 3(\mathrm{mod}4).\end{array}$
Објашњење за $(\ast )$: Фактор $\frac{p-1}{2}$ је тачно онда паран број, када непаран број $p$ при дељењу са $4$ даје остатак $1$. На пример, $\frac{5-1}{2}=2$ (паран), али $\frac{7-1}{2}=3$ (непаран), и $5$ има остатак $1$ односно $7$ има остатак $3$ при дељењу са $4$. Производ $mn$ целих бројева је коначно тачно онда паран, када је барем један фактор паран, и $(-1{)}^{mn}$ је стога тачно онда позитиван, када је барем један од фактора $m$ или $n$ паран.

Поред тога, постоје два тзв. допунска става, која омогућавају директно израчунавање вредности $\left(\frac{-1}{p}\right)$ односно $\left(\frac{2}{p}\right)$ за непарне просте бројеве $p$.

1. допунски став: За сваки непаран прост број $p$ важи:
$\left(\frac{-1}{p}\right)=(-1{)}^{\frac{p-1}{2}}=\{\begin{array}{cc}1& p\equiv 1(\mathrm{mod}4),\\ -1& p\equiv 3(\mathrm{mod}4).\end{array}$

2. допунски став: За сваки непаран прост број $p$ важи:
$\left(\frac{2}{p}\right)=(-1{)}^{\frac{p^2-1}{8}}\stackrel{(\ast \ast )}{=}\{\begin{array}{cc}1& p\equiv \pm 1(\mathrm{mod}8),\\ -1& p\equiv \pm 3(\mathrm{mod}8).\end{array}$
Објашњење за $(\ast \ast )$: Важи према трећој биномној формули $p^2-1=(p-1)(p+1)$. Пошто је $p$ непаран, један од фактора $p\pm 1$ је дељив са $4$, а други са $2$. Стога је $\frac{p^2-1}{8}$ увек цео број. Са $p\equiv \pm 1(\mathrm{mod}8)$ се може постићи да је фактор $p\mp 1$ чак дељив са $8$, чиме је $\frac{p^2-1}{8}$ паран број. У случајевима $p\equiv \pm 3(\mathrm{mod}8)$ то се не може постићи, и $\frac{p^2-1}{8}$ је непаран.

Ако су $p$ и $q$ два различита непарна проста броја, последично важи:

$\left(\frac{p}{q}\right)=\{\begin{array}{cc}-\left(\frac{q}{p}\right)& \text{за}p\equiv q\equiv 3(\mathrm{mod}4)\\ \left(\frac{q}{p}\right)& \text{иначе}\end{array}$

Јер из $\left(\frac{p}{q}\right)\in \{-1,1\}$ већ следи ${\left(\frac{p}{q}\right)}^{-1}=\left(\frac{p}{q}\right)$.

Историја

Пјер де Ферма

Прве назнаке квадратног закона реципроцитета налазе се у радовима Пјера де Ферма. Фермаови резултати о представљању целих бројева као збира два квадрата директно су довели до проблема одређивања квадратног карактера $-1$, дакле до проналажења $\left(\frac{-1}{p}\right).$ Ферма је успео да карактерише оне непарне просте бројеве који се могу написати као збир одређених комбинација квадратних бројева. Тако је показао

$p=x^2+y^2,x,y\in \mathbb{Z}⟺p\equiv 1(\mathrm{mod}4).$

На пример, једначине

$5=1+4,13=4+9,17=1+16,29=4+25,37=1+36,\dots$

показују прве непарне просте бројеве који се могу написати као збир два квадрата. То су тачно они прости бројеви који при дељењу са $4$ дају остатак $1$. Ферма је уопштеније истраживао и представљање простих бројева квадратним формама облика $q(x,y)=x^2+n{y}^2$, где је $n\in \{\pm 2,\pm 3,-5\}$. Тврдио је, на пример, да је

$p=x^2+2y^2,x,y\in \mathbb{Z}⟺p\equiv 1,3(\mathrm{mod}8)$

$p=x^2+3y^2,x,y\in \mathbb{Z}⟺p=3,$ или $p\equiv 1(\mathrm{mod}3),$

али је могуће доказе само наговестио. Када је $n\in \{2,3\}$, може се показати да прост број $p$ који дели $x^2+n{y}^2$, а притом не дели ни $x$ ни $y$, и сам има облик $p=a^2+n{b}^2$ за пар целих бројева $a$ и $b$. Из ове чињенице се може закључити да се $p$ може представити квадратним формама $x^2+2y^2$ или $x^2+3y^2$ тачно онда када је $-2$ односно $-3$ квадратни остатак од $p$. На пример, прост број $p=79$ је облика $x^2+3y^2$, јер је

$79=4+75=4+3\cdot 25=2^2+3\cdot 5^2.$

Заиста, $-3$ је квадратни остатак модуло $79$, јер $79$ дели број $32^2+3=1027=13\cdot 79$. Из тог разлога су и експлицитни изрази $\left(\frac{-2}{p}\right)$ и $\left(\frac{-3}{p}\right)$ већ код Фермаа били од значаја.

Жозеф-Луј Лагранж

Леонард Ојлер

Квадратни закон реципроцитета први пут је открио Леонард Ојлер, који га је емпиријским истраживањима сматрао тачним, али није могао да пружи доказ. Леополд Кронекер је указао да он, између осталог, брзо следи из једне Ојлерове претпоставке из његовог списа Theoremata circa divisores numerorum in hac forma $p{a}^2\pm q{b}^2$ contentorum (1744–1746). Након тога, Ојлер се више од две деценије посветио другим темама. Тек истраживања Жозефа-Луја Лагранжа у годинама 1773. до 1775, посебно његови радови на општој теорији бинарних квадратних форми, коначно су подстакли Ојлера да се поново детаљно посвети проучавању квадратних остатака. Лагранж је желео да унапреди истраживања о математичким идејама које су покренули Ферма и Ојлер. Експлицитним одређивањем $\left(\frac{\pm 2}{p}\right)$, $\left(\frac{\pm 3}{p}\right)$ и $\left(\frac{\pm 5}{p}\right)$ за непарне просте бројеве $p$, успео је да карактерише просте бројеве са представом $x^2+5y^2$ као и $2x^2+2xy+3y^2$. На крају својих излагања, Лагранж је сажео све што је могао рећи о квадратном реципроцитету. Своје резултате је увек формулисао у терминима тзв. Ојлеровог критеријума

$a^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right)(\mathrm{mod}p)(\mathrm{n}\mathrm{z}\mathrm{d}(a,p)=1),$

који представља уопштење мале Фермаове теореме. Забележио је да је за прост број $p$ облика $8n\pm 1$ вредност $2^{\frac{p-1}{2}}-1$ већ дељива са $p$, а за оне облика $8n\pm 3$ је $2^{\frac{p-1}{2}}+1$ дељиво са $p$. Лагранж се тиме сматра откривачем 2. допунског става. У свом раду Observationes circa divisionem quadratorum per numeros primos, који је објављен 1783. постхумно, Ојлер је коначно дао формулацију квадратног закона реципроцитета која је веома блиска данас најчешће коришћеној. У модерној нотацији она гласи:

Нека је $p$ непаран прост број и $a$ цео број који није дељив са $p$. Ако је $q$ прост број такав да је $p\equiv \pm q(\mathrm{mod}4a)$, онда важи $\left(\frac{a}{p}\right)=\left(\frac{a}{q}\right)$.

Ово казује да вредност $\left(\frac{a}{p}\right)$ Лежандровог симбола зависи само од класе остатака $p$ модуло $4a$, и да је вредност иста за све просте бројеве који при дељењу са $4a$ дају исти остатак $r$ односно $4a-r$. Елементарно је показано да је ова верзија коју је формулисао Ојлер еквивалентна квадратном закону реципроцитета.

Још у истом веку квадратни закон реципроцитета поново је открио Адријен-Мари Лежандр и 1785. објавио у свом раду Recherches d’Analyse Indéterminée. Лежандр је успео да га, уз помоћ свог доказа Лежандрове теореме објављеног у том раду, докаже у специјалним случајевима. Његова теорема се бави довољним и неопходним условима за постојање целобројних решења $(x,y,z)≠(0,0,0)$ једначине

$a{x}^2+b{y}^2+c{z}^2=0(a,b,c\in \mathbb{Z}).$

Посматрајући специјалну једначину

$x^2+p{y}^2-q{z}^2=0$

са простим бројевима $p\equiv 1(\mathrm{mod}4)$ и $q\equiv 3(\mathrm{mod}4)$, успео је да покаже да ако је $q$ квадратни остатак модуло $p$, онда је и $p$ квадратни остатак модуло $q$. Лежандр је, даље, доказиво био под утицајем Лагранжа, али је други допунски став формулисао на другачији начин. Није говорио о „дељивости $2^{p-1}-1$ са $p$“, већ је користио нотацију $2^{p-1}=1$, упозоравајући читаоце да се ова једнакост треба разумети само до на вишекратнике од $p$. Након ових излагања о специјалном случају 2. допунског става, Лежандр је формулисао, изузев нотације, данас уобичајену верзију квадратног закона реципроцитета:

Ако су $c$ и $d$ два непарна проста броја, изрази $c^{\frac{d-1}{2}}$ и $d^{\frac{c-1}{2}}$ неће имати различите предзнаке, осим ако су $c$ & $d$ оба облика $4n-1$. У свим осталим случајевима имаће исти предзнак.

Лежандров доказ је, међутим, имао недостатке. Очигледно незадовољан дотадашњим резултатима, Лежандр је 1798. објавио много амбициознији рад под насловом Essai sur la Théorie des Nombres, у којем је, између осталог, увео данас уобичајену нотацију $\left(\frac{a}{p}\right)$ за Лежандров симбол. У поглављу под насловом „Теорема која садржи закон реципроцитета који постоји између било која два проста броја“, Лежандр је коначно формулисао правило

$\left(\frac{n}{m}\right)=(-1{)}^{\frac{n-1}{2}\frac{m-1}{2}}\left(\frac{m}{n}\right)$,

из којег потиче данашња нотација. Међутим, Essai је садржао само понављање непотпуног доказа из 1785. Овај се заснивао на претпоставци да за сваки прост број $p$ облика $4n+1$ постоји други прост број $q$ облика $4n+3$, тако да је $\left(\frac{p}{q}\right)=-1$. Лежандр, међутим, није могао да докаже ову тврдњу. Назив „закон реципроцитета“ („Loi de reciprocité“) такође потиче од Лежандра.

Карл Фридрих Гаус 1803. године

Први потпуни доказ дао је Карл Фридрих Гаус 1801. године у свом за модерну теорију бројева пионирском делу Disquisitiones Arithmeticae. Међутим, Гаус је, доказиво, такав доказ имао већ 1796, у доби од деветнаест година. То произилази из Гаусовог математичког дневника, у којем је доказ датирао на 8. април 1796. Он је написао, у суштини: „Открили смо фундаменталну теорему индукцијом у марту 1795. Први доказ, онај у овом одељку, пронашли смо у априлу 1796.“. Пошто је Гаус овом резултату придавао централни значај, изабрао је назив „фундаментална теорема“ и написао: „Пошто скоро све што се може рећи о квадратним остацима зависи од ове теореме, назив фундаментална теорема, који ћемо од сада користити, требало би да буде прихватљив.“ Гаусов најављени доказ био је предмет параграфа 135–144 у Disquisitiones. Један од разлога зашто је Гаус потпуно игнорисао нотацију коју је увео Лежандр био је тај што су његова истраживања текла независно.

Само Гаусу се приписује најмање осам методички различитих доказа. Гаус сам никада није користио појам „квадратни закон реципроцитета“. Уместо тога, теорему је, поред фундаменталне теореме, називао „Theorema aureum“ (српски: „Златна теорема“) теорије бројева. Квадратни закон реципроцитета био је само полазна тачка за откриће читавог низа, делом много дубљих, виших закона реципроцитета. Ову иницијативу је још сам Гаус покренуо. Тако се бавио и кубном и биквадратном реципрочношћу, и иако нешто није објавио, сматра се вероватним да је имао одговарајуће доказе за своје тврдње. Само о биквадратном случају, дакле о случају четвртог степена, постоје Гаусове публикације из 1828. и 1832. године. Први потпуни објављени докази за кубну односно биквадратну реципрочност потичу од Готхолда Ајзенштајна односно Карла Густава Јакобија. У наредним деценијама, на крају веома дубоке структуре иза квадратног закона реципроцитета откривене су развојем тзв. теорије поља класа. Веома општи и свеобухватни Артинов закон реципроцитета (назван по Емилу Артину) успео је почетком 20. века коначно да уједини све до тада познате законе реципроцитета и дао је делимичан одговор на девети Хилбертов проблем. Са алатима теорије поља класа, коначно је, већ интензивно проучавано питање, између осталих, од стране Фермаа, Ојлера, Лагранжа, Лежандра и Гауса о представљању простих бројева облика $x^2+n{y}^2$ у пуној општости, дакле за све природне бројеве $n$, одговорено.

До данас је објављено више од 300 доказа. За историјску позадину неких од ових доказа, видети у истоименом одељку.

Значај и примене

Брзо израчунавање Лежандровог симбола

Квадратни закон реципроцитета пружа могућност брзог израчунавања Лежандровог симбола $\left(\frac{a}{p}\right)$ и тиме одлучивања да ли је $a$ квадратни остатак модуло $p$ или не. За то је, међутим, потребно да се $a$ у разумном времену растави на просте факторе. У поступку се комбиновано користе мултипликативност и периодичност Лежандровог симбола, као и квадратни закон реципроцитета са допунским ставовима.

Пример је израчунавање $\left(\frac{219}{383}\right)$, да би се одлучило да ли је $219$ квадратни остатак модуло простог броја $383$. Прво се $219$ раставља на просте факторе $219=3\cdot 73$. Са мултипликативношћу Лежандровог симбола добија се

$\left(\frac{219}{383}\right)=\left(\frac{3}{383}\right)\left(\frac{73}{383}\right).$

Сада има смисла разматрати оба фактора на десној страни одвојено. Са квадратним законом реципроцитета и $3$-периодичношћу Лежандровог симбола $\left(\frac{\cdot }{3}\right)$ важи, с једне стране,

$\left(\frac{3}{383}\right)=\underset{=-1}{\underbrace{(-1{)}^{\frac{3-1}{2}\cdot \frac{383-1}{2}}}}\left(\frac{383}{3}\right)=-\left(\frac{2}{3}\right)=(-1{)}^2=1.$

Притом је у претпоследњем кораку коришћено да $2$ није квадратни остатак модуло $3$ (што је, на пример, јасно из провере, и не треба више доказивати). С друге стране, опет помоћу квадратног закона реципроцитета и $73$-периодичности од $\left(\frac{\cdot }{73}\right)$, важи да је

$\left(\frac{73}{383}\right)=\underset{=1}{\underbrace{(-1{)}^{\frac{73-1}{2}\frac{383-1}{2}}}}\left(\frac{383}{73}\right)=\left(\frac{18}{73}\right).$

Са $18=2\cdot 3^2$ има се, коришћењем 2. допунског става,

$\left(\frac{18}{73}\right)=\left(\frac{2}{73}\right)\underset{=1}{\underbrace{{\left(\frac{3}{73}\right)}^2}}=\left(\frac{2}{73}\right)=(-1{)}^{\frac{73^2-1}{8}}=1.$

Укупно следи да је

$\left(\frac{219}{383}\right)=\left(\frac{3}{383}\right)\left(\frac{73}{383}\right)=1\cdot 1=1.$

Тиме је $219$ квадратни остатак модуло $383$. На пример,

$169^2-219=28342=74\cdot 383$

је дељив са $383$. (Напомена: оригинални текст имао је грешку 28342 = 2 * 37 * 383, што је нетачно. 2 * 37 = 74).

Докази са нултим знањем

Квадратни остаци, као и квадратни закон реципроцитета, могу се користити у криптографији за поступак доказа са нултим знањем.

Доказ са нултим знањем може са великом вероватноћом доказати да неко зна тајну, а да је не открије. Заснива се на комуникацији две стране, доказивача и верификатора. Притом, доказивач покушава да убеди верификатора да поседује тајну информацију, а да је не открије. Верификатор тада, у зависности од сврхе поступка, може извући своје закључке. На пример, могао би бити релативно сигуран да комуницира са одређеном особом, рецимо непосредно пре новчане трансакције, јер само та особа може знати тајну. Основа је увек та да на основу информација које доказивач ставља на располагање јавности, за спољне посматраче није могуће у разумном временском року доћи до тајне.

Тајна не мора бити „осетљива информација“, као што је државна тајна. Може се радити само о бројчаном коду, за који се, међутим, претпоставља да га само доказивач, по имену Алиса, зна, јер се налази искључиво у њеном сефу. Ако верификатор Боб сада жели да се увери да се заиста ради о Алиси, може проверити да ли особа са друге стране везе заиста зна код. За то се може поступити на следећи начин.

1. Прво, Алиса, на пример уз помоћ одговарајућег теста простоте броја, бира два веома велика различита проста броја $p$ и $q$. Они би требало, ради сигурности, да имају неколико стотина цифара. На пример, $p=31$ и $q=61$ би били потпуно неприкладни, али ће у наставку служити као пример.
2. Сада Алиса формира производ $n$ два проста броја, дакле $n:=pq$. Овај поступак на неки начин личи на „затварање сигурносних врата“, јер иако је веома лако израчунати производ $pq$ (теоријски чак и ручно), обрнути поступак, дакле факторизација $n$ у његова (два) проста фактора, је код неколико стотина децималних места изузетно тежак проблем, за који до данас не постоји брз математички поступак (види такође поступци факторизације). Само Алиса поседује „приватни кључ“ $(p,q)$, јер је она изабрала просте бројеве $p$ и $q$, и стога $n$ уопште не мора да факторише. У примеру је $n=31\cdot 61=1891$.
3. Код $(p,q)$, дакле $(31,61)$, сада је Алисина тајна. Она, међутим, може без бриге објавити производ $n$, јер ниједан суперрачунар данашњице није у стању да из тога добије $(p,q)$. Исто тако, Алиса објављује лични идентификациони број, на пример $I=391$, како би, на пример, при захтеву за верификацију брже била пронађена у Бобовом „адресару“.
4. Алиса жели да саопшти Бобу да зна код $(31,61)$, а да Бобу не открије која је његова вредност. У супротном, на пример, Боб, или његов најбољи пријатељ Јустус, који случајно седи код Боба у соби, могли би украсти бројеве $(31,61)$ од Алисе и убудуће се представљати као она. У ту сврху, она на свој ID $I=391$ евентуално додаје још неколико случајних цифара, док се не добије квадратни остатак $v$ од $n=1891$. У примерном случају то више није потребно, јер Алиса препознаје да је већ $I=v=391$ квадратни остатак модуло $1891$ (за овај доказ може користити квадратни закон реципроцитета). За то користи чињеницу да зна факторизацију $n$. Алиса сада шаље Бобу одговарајући квадратни корен од $v=391$ модуло $1891$. Такав је, на пример, $u=239$, јер је $u^2-v=239^2-391=56730=30\cdot 1891$ дељив са $p=31$ и $q=61$, дакле са $n=1891$. Дакле, $u^2\equiv v(\mathrm{mod}1891)$. За то Алиса мора симултано решити само конгруенције $x^2\equiv v(\mathrm{mod}31)$ и $x^2\equiv v(\mathrm{mod}61)$. Потенцијални нападач не би био у стању да „извади овај квадратни корен модуло $n$“, јер то, без познавања просте факторизације $n$, до данас није решиво у разумном времену.
5. Алиса сада користи овај квадратни корен $u$ модуло $n$ из $v$, којим само она може располагати, да би показала да заиста располаже са $(p,q)$. У ту сврху, Боб подвргава Алису неколико тестова. Она их може са 100-постотном вероватноћом тачно одговорити само ако располаже са $u$. Ако то не чини, њен одговор је тачан само са око 50 посто. Боб, међутим, може у дугој петљи стално постављати тест питања. Вероватноћа да нападач погоди сваки одговор рапидно тежи 0 са повећањем броја питања. Једноставно речено, у овом тесту се дешава следеће: Алиса случајно генерише број $x$ узајамно прост са $n$, и уз помоћ $u$ из њега други број $y$. Дакле, $x$ и $y$ су у вези преко тајног квадратног корена $u$ од $v$ модуло $n$. Затим шаље оба броја Бобу. Боб, међутим, није у стању да из њих прочита $u$. Он затим, помоћу генератора случајности облика 50:50, на пример савршеног бацања новчића, тестира Алису да ли је теоријски у стању да истовремено из $x$ и $y$ извуче квадратни корен модуло $n$. Он, међутим, случајно бира само један од бројева $x$ („глава“) или $y$ („писмо“). Алиса затим шаље одговарајући резултат, који Боб квадрирањем брзо може идентификовати као квадратни корен модуло $n$. Одлучујућа ствар је да Алиса не зна из ког броја ће морати да извуче корен модуло $n$ (тачније, већ и „одговарајућа“ конструкција оба вредности $x$ и $y$ без $u$ не би била могућа). Да јој је то унапред познато, могла би проћи тест и без $u$, међутим, $u$ је неопходан да би се адекватно одговорило на сваки Бобов захтев. С друге стране, поступком се Алиси осигурава да ће Боб увек добити само један резултат. Тиме се обезбеђује да он никада неће бити у стању да израчуна $u$, чиме $u$ остаје сигурно сачуван. Алиса у сваком пролазу бира два нова броја $x$ и $y$.

Овај поступак је 1985. године развио Ади Шамир.

Детаљи о Бобовом тесту

Боб на почетку располаже бројевима $n=1891$ и $v=I=391$. Он жели да тестира да ли Алиса заиста располаже бројем $u$. За то се следећа тест петља може понављати произвољно често, док се Боб не увери у довољној мери: Алиса бира случајни остатак $r$ модуло $n$, и пази само да су $n$ и $r$ узајамно прости. То може веома брзо тестирати помоћу Еуклидовог алгоритма. За $r$ сада генерише остатак $x\equiv r^2(\mathrm{mod}n)$ (једноставним квадрирањем $r$) и $y\equiv v{x}^{-1}(\mathrm{mod}n)$ (сваки са репрезентантима $0<x,y<n$ модуло $n$). Притом, $x^{-1}$ има особину $x{x}^{-1}\equiv 1(\mathrm{mod}n)$ и може се брзо пронаћи помоћу проширеног Еуклидовог алгоритма. Егзистенција је обезбеђена са $1=\mathrm{n}\mathrm{z}\mathrm{d}(r,n)=\mathrm{n}\mathrm{z}\mathrm{d}(r^2,n)=\mathrm{n}\mathrm{z}\mathrm{d}(x,n)$. Ако, на пример, изабере $r=998$, добија $x\equiv 998^2\equiv 1338(\mathrm{mod}1891)$ и $y\equiv v{x}^{-1}\equiv 391\cdot 1296\equiv 1839(\mathrm{mod}1891)$. Алиса шаље вредности $x$ и $y$ Бобу. Боб проверава да ли заиста важи $xy\equiv v(\mathrm{mod}n)$ (што би због $xy\equiv vx{x}^{-1}(\mathrm{mod}n)$ требало бити испуњено). Он налази, на пример, $1338\cdot 1839\equiv 391(\mathrm{mod}1891)$. Сада бира случајни бит $b\in \{0,1\}$, на пример $b=1$. Овај шаље Алиси. Ако је овај бит $b=0$, Алиса шаље остатак $r$ назад Бобу. Ако је, међутим, $b$ једнако $1$, Алиса шаље остатак $0<s:=u{r}^{-1}<n$ Бобу. Боб сада израчунава квадрате броја који му је Алиса послала. У случају $b=0$ проверава $r^2\equiv x(\mathrm{mod}n)$, а у случају $b=1$ проверава $s^2\equiv y(\mathrm{mod}n)$. Само ако Алиса располаже са $u$, може истовремено располагати са $r$ и $s$, јер по конструкцији важи $rs\equiv u(\mathrm{mod}n)$. Сходно томе, важно је да Боб увек добије само један од ових бројева, како не би сам могао израчунати $u$.

Детаљи о томе како Алиса може вадити квадратне корене модуло $n$

Пошто Алиса зна просту факторизацију $n=p\cdot q$, да би могла извадити квадратни корен из $v$, потребно је само да реши симултане конгруенције $x^2\equiv v(\mathrm{mod}p)$ и $x^2\equiv v(\mathrm{mod}q)$. Наиме, ако и $p$ и $q$ деле број $x^2-v$, онда и њихов производ $n$ дели тај број (на пример, број дељив са $2$ и $3$ је увек дељив са $6$). За решивост мора важити $\left(\frac{v}{p}\right)=\left(\frac{v}{q}\right)=1$, што се може проверити, евентуално, помоћу квадратног закона реципроцитета (шанса за успех је око 50 посто). Ако је то случај, у случају $p\equiv q\equiv 3(\mathrm{mod}4)$ може се брзо поступити на следећи начин: Са Ојлеровим критеријумом важи $v^{\frac{1}{2}(p-1)}\equiv \left(\frac{v}{p}\right)=1(\mathrm{mod}p),v^{\frac{1}{2}(q-1)}\equiv \left(\frac{v}{q}\right)=1(\mathrm{mod}q),$ дакле важи ${\left(v^{\frac{1}{4}(p+1)}\right)}^2=v^{\frac{1}{2}(p-1)}v\equiv v(\mathrm{mod}p)$ и аналогно ${\left(v^{\frac{1}{4}(q+1)}\right)}^2\equiv v(\mathrm{mod}q).$ Са Кинеском теоремом о остацима сада се може брзо решити симултана конгруенција $u\equiv v^{\frac{1}{4}(p+1)}(\mathrm{mod}p)$ $u\equiv v^{\frac{1}{4}(q+1)}(\mathrm{mod}q)$ и пронађен је квадратни корен $u$ од $v$ модуло $n$. Постоје и брзи, али компликованији, алгоритми за случај да је барем један од простих бројева $\equiv 1(\mathrm{mod}4)$.

Квадратни закон реципроцитета може се користити на одлучујућем месту где доказивач мора да генерише квадратни остатак $v$ из свог ID-а $I$. За то се мора израчунати да ли заиста

$\left(\frac{v}{p}\right)=\left(\frac{v}{q}\right)=1$

важи. Ако доказивач зна просту факторизацију $v$, на пример зато што $v$ није превелик, ово је прилично ефикасно средство. Међутим, неопходност просте факторизације $v$ за велике вредности постаје све већи проблем. Ипак, постоји алтернативни алгоритам за брзо израчунавање Лежандровог симбола без потребе за растављањем $v$ на просте факторе. Он личи на Еуклидов алгоритам. Али квадратни закон реципроцитета игра значајну улогу у верификацији ове методе.

Решавање квадратних конгруенција

Брзо израчунавање Лежандрових симбола помоћу квадратног закона реципроцитета може помоћи да се брзо одлучи да ли је квадратна конгруенција облика

$a{x}^2+bx+c\equiv 0(\mathrm{mod}p)$

са $a,b,c\in \mathbb{Z}$ и $\mathrm{n}\mathrm{z}\mathrm{d}(p,a)=1$ решива, где је $p$ непаран прост број. Ово се може тумачити као квадратна једначина

$\bar{a}{x}^2+\bar{b}x+\bar{c}=\bar{0}(\bar{a}≠\bar{0}),$

над коначним пољем ${𝔽}_p=\{\bar{0},\dots ,\overline{p-1}\}$. Дискриминанта $D={\bar{b}}^2-\overline{4ac}$ мора бити квадрат у ${𝔽}_p$ да би постојало решење. Тачније, постоји

$1+\left(\frac{b^2-4ac}{p}\right)$

решења. Са квадратним законом реципроцитета, ако се може наћи проста факторизација $b^2-4ac$, Лежандров симбол $\left(\frac{b^2-4ac}{p}\right)$ се може брзо израчунати.

Ако се може одлучити да ли квадратне конгруенције модуло произвољних простих бројева имају решење, то се у неким случајевима може постићи и за конгруенције са произвољним модулом $m$. Дакле, ако се посматра конгруенција

$a{x}^2+bx+c\equiv 0(\mathrm{mod}m),(a,b,c\in \mathbb{Z},a\equiv ̸0(\mathrm{mod}m))$

, она је, ако је $m=p_1^{c_1}\cdots p_r^{c_r}$ (са $c_j\ge 1$), решива тачно онда када је свака од „локалних“ конгруенција

$a{x}^2+bx+c\equiv 0(\mathrm{mod}{p}_j^{c_j})$

решива. Ово је последица тзв. Кинеске теореме о остацима, и тиме је проблем већ сведен на случај степена простог броја. У случају да је $\mathrm{n}\mathrm{z}\mathrm{d}(b^2-4ac,m)=1$ и $m$ непаран, ове конгруенције су решиве тачно онда када су решиве све конгруенције

$y^2\equiv b^2-4ac(\mathrm{mod}{p}_j)$

. За паран $m$ или у случају да дискриминанта $D=b^2-4ac$ није узајамно проста са $m$, ово више није безусловно тачно, и мора се поступити другачије.

Расподела квадратних остатака и неостатака

Већ је Ојлер установио да пресликавање

$p\mapsto \left(\frac{a}{p}\right)(a\in \mathbb{Z}\setminus \{0\})$

на простим бројевима зависи само од класе остатака простог броја $p$ модуло $4a$. Ово пресликавање дефинише тзв. квадратни Дирихлеов карактер модуло $4|a|$, тако што се дефинише као $0$ на $p=2$ и затим преко просте факторизације мултипликативно проширује на све целе бројеве. Дакле, ако је $m=p_1^{r_1}\cdots p_{\ell }^{r_{\ell }}$, дефинише се

$\left(\frac{a}{m}\right):={\left(\frac{a}{p_1}\right)}^{r_1}\cdots {\left(\frac{a}{p_{\ell }}\right)}^{r_{\ell }},$

при чему су вредности $\left(\frac{a}{p_1}\right),\dots ,\left(\frac{a}{p_{\ell }}\right)$ већ све објашњене Лежандровим симболом. Да би се феномену $4|a|$-периодичности дало више значаја, користи се чињеница да је $4$ квадратни број, па мултипликативно не мења Лежандров симбол, и алтернативно се посматра $\left(\frac{4a}{m}\right)=\left(\frac{a}{m}\right)$. У случају да је $a$ без квадрата, ради се о тзв. примитивном реалном карактеру (а $4a$ се назива фундаментална дискриминанта).

Ова Ојлерова изјава је, као што се данас зна, еквивалентна квадратном закону реципроцитета и има непосредне последице на расподелу квадратних (не-)остатака. Тако је, на пример, $7$ квадратни неостатак модуло $11$, али тиме и модуло простог броја $11+2\cdot 28=67$ (пошто је $28=4\cdot 7$), па важи

$\left(\frac{7}{11}\right)=\left(\frac{7}{67}\right)=-1$.

Изјаве о бесконачности и асимптотика

Различите изјаве о „учесталости“ квадратних остатака могу се доказати помоћу квадратног закона реципроцитета. Док доказ чињенице да за цео број $a≠0$ постоји бесконачно много простих бројева $p$ тако да је $a$ квадратни остатак модуло $p$ не захтева квадратни закон реципроцитета, тек се уз његову помоћ може показати да је сваки број $a\in \mathbb{Z}$ који није квадратни број, бесконачно често квадратни неостатак неког простог броја $p$. Особина бити квадратни број је, штавише, и довољна и неопходна да би тај број за све (осим коначно много) просте бројеве $p$ био квадратни остатак модуло $p$. Ове изјаве се могу, такође уз употребу квадратног закона реципроцитета, у неким случајевима подићи на асимптотику за коначне скупове. Притом су се горњи случајеви увек односили на једночлане скупове $\{a\}$. За то се мора објаснити појам асимптотске густине скупа $\mathrm{\Pi }\subset \mathbb{P}$ унутар скупа свих простих бројева $\mathbb{P}$. Она је, ако постоји, дата са

$\delta (\mathrm{\Pi }):=\underset{x\to \mathrm{\infty }}{lim}\frac{|\{p\le x:p\in \mathrm{\Pi }\}|}{\pi (x)}=\underset{x\to \mathrm{\infty }}{lim}\frac{\text{Број простих бројева}\le x\text{из}\mathrm{\Pi }}{\text{Број простих бројева}\le x}$,

где је $\pi (x)$ број свих простих бројева до величине $x$. Природно је да увек важи $0\le \delta (\mathrm{\Pi })\le 1$. Ако је ${\mathrm{\Pi }}_0$, на пример, само коначан скуп простих бројева, онда из Еуклидова теорема већ следи $\delta ({\mathrm{\Pi }}_0)=0$. С друге стране, важи $\delta (\mathbb{P})=1$. Мајкл Филасета и Дејвид Ричман су 1989. године, користећи квадратни закон реципроцитета и јаку форму Дирихлеове теореме о простим бројевима, показали да за сваки непразан коначан скуп $P\subset \mathbb{P}$ и сваку функцију $\epsilon :P\to \{-1,1\}$ асимптотска густина скупа

${\mathrm{\Pi }}_P:=\{p\in {\mathbb{P}}_{>2}:\left(\frac{q}{p}\right)=\epsilon (q)\text{за све}q\in P\}$

има вредност $\frac{1}{2^{|P|}}$. Ако је, на пример, $P=\{29\}$ и $\epsilon (29):=1$, онда скуп непарних простих бројева у односу на које је $29$ квадратни остатак, дакле

${\mathrm{\Pi }}_{\{29\}}=\{p\in {\mathbb{P}}_{>2}:\left(\frac{29}{p}\right)=1\}$

има асимптотску густину $\frac{1}{2}$, јер $P$ има само један елемент, $|P|=|\{29\}|=1$. Дакле, асимптотски гледано, у просеку сваки други прост број има прост број $29$ као квадратни остатак. Следећа табела визуелизује ситуацију за прве просте бројеве $3\le p\le 197$:

$p$	3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61	67	71	73	79	83	89	97	101	103	107	109	113	127	131	137	139	149	151	157	163	167	173	179	181	191	193	197
$\left(\frac{29}{p}\right)$	−1	1	1	−1	1	−1	−1	1	0	−1	−1	−1	−1	−1	1	1	−1	1	1	−1	−1	1	−1	−1	−1	1	1	1	−1	−1	−1	−1	1	1	1	−1	−1	1	1	1	1	−1	−1	1

Аналогно, на пример, у просеку сваки четврти прост број $p$ има својство да је истовремено

$\left(\frac{29}{p}\right)=1$ и $\left(\frac{61}{p}\right)=-1$

испуњено. Треба напоменути да постоје тачно четири могућности за пресликавање вредности $29$ и $61$ на $\pm 1$. Следећа табела визуелизује ситуацију за прве просте бројеве $3\le p\le 197$:

$p$	3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61	67	71	73	79	83	89	97	101	103	107	109	113	127	131	137	139	149	151	157	163	167	173	179	181	191	193	197
$\left(\frac{29}{p}\right)$	−1	1	1	−1	1	−1	−1	1	0	−1	−1	−1	−1	−1	1	1	−1	1	1	−1	−1	1	−1	−1	−1	1	1	1	−1	−1	−1	−1	1	1	1	−1	−1	1	1	1	1	−1	−1	1
$\left(\frac{61}{p}\right)$	1	1	−1	−1	1	−1	1	−1	−1	−1	−1	1	−1	1	−1	−1	0	−1	−1	1	−1	1	−1	1	−1	1	1	1	1	1	1	1	−1	1	−1	−1	1	1	−1	1	−1	−1	−1	1

Уопштено, постоји $2^{|P|}$ могућности за пресликавање коначног скупа $P$ у $\{\pm 1\}$. Стога, резултат увек предвиђа дугорочну равномерну расподелу унутар свих могућности.

Постојање неостатака у одређеним интервалима

У питању постојања квадратних неостатака у одређеним областима, постигнут је напредак уз помоћ квадратног закона реципроцитета. Тако се уз његову помоћ може показати да за сваки прост број $q>3$ постоји већ прост број $2<p<8(\sqrt{q}+1)$ тако да је $\left(\frac{q}{p}\right)=-1$. Стога се не може десити да је $q$ квадратни остатак за „произвољно много простих бројева“. За доказ ове чињенице, поред квадратног закона реципроцитета, потребна је и процена

$\left|\sum _{\genfrac{}{}{0ex}{}{u\in S}{v\in T}}\left(\frac{u+v}{p}\right)\right|\le \sqrt{p|S||T|}$

при чему се захтева да ниједна два цела броја у коначним скуповима $S,T\subset \mathbb{Z}$ нису конгруентна модуло $p$.

Гаус је приметио да се у случају простих бројева $q\equiv 1(\mathrm{mod}8)$ постојање простог броја $2<p<2\sqrt{q}+1$ са $\left(\frac{q}{p}\right)=-1$ може доказати и без употребе квадратног закона реципроцитета.

Визуелизација

Квадратни закон реципроцитета може се, према Лежандровој формулацији, визуелизовати на следећи начин. У следећој табели, у редовима и колонама су уписани први прости бројеви. У редовима, прост број одређује модуо, а бојом је означено да ли је прост број у одговарајућој колони квадратни остатак или неостатак. Плава и зелена поља су потпуно симетрична у односу на дијагоналу; она одговарају случајевима када барем један од простих бројева при дељењу са $4$ даје остатак $1$. У том случају заиста важи

$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=1,$

чиме у оба случаја морају постојати или остаци или неостаци: заиста, пошто је резултат израза $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)$ позитиван, оба фактора морају имати или вредност $+1$ или вредност $-1$. Дакле, питања о квадратним остацима у оба случаја симултано се одговарају са „да” или са „не”. Ако, пак, оба проста броја при дељењу са $4$ дају остатак $3$, онда важи

$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=-1,$

и увек мора постојати тачно један остатак и тачно један неостатак, односно оба члана имају различит предзнак $\pm 1$. Због тога се овде црвено поље пресликава у наранџасто поље на дијагонали, и обрнуто.

Легенда

R	q је квадратни остатак (мод p)	q ≡ 1 (mod 4) или p ≡ 1 (mod 4)
N	q је квадратни неостатак (мод p)
R	q је квадратни остатак (мод p)	q ≡ 3 (mod 4) и p ≡ 3 (mod 4)
N	q је квадратни неостатак (мод p)

		q
		3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61	67	71	73	79	83	89	97
p	3		N	R	N	R	N	R	N	N	R	R	N	R	N	N	N	R	R	N	R	R	N	N	R
	5	N		N	R	N	N	R	N	R	R	N	R	N	N	N	R	R	N	R	N	R	N	R	N
	7	N	N		R	N	N	N	R	R	N	R	N	R	N	R	N	N	R	R	N	R	N	N	N
	11	R	R	N		N	N	N	R	N	R	R	N	N	R	R	R	N	R	R	N	N	N	R	R
	13	R	N	N	N		R	N	R	R	N	N	N	R	N	R	N	R	N	N	N	R	N	N	N
	17	N	N	N	N	R		R	N	N	N	N	N	R	R	R	R	N	R	N	N	N	R	R	N
	19	N	R	R	R	N	R		R	N	N	N	N	R	R	N	N	R	N	N	R	N	R	N	N
	23	R	N	N	N	R	N	N		R	R	N	R	N	R	N	R	N	N	R	R	N	N	N	N
	29	N	R	R	N	R	N	N	R		N	N	N	N	N	R	R	N	R	R	N	N	R	N	N
	31	N	R	R	N	N	N	R	N	N		N	R	N	R	N	R	N	R	R	N	N	N	N	R
	37	R	N	R	R	N	N	N	N	N	N		R	N	R	R	N	N	R	R	R	N	R	N	N
	41	N	R	N	N	N	N	N	R	N	R	R		R	N	N	R	R	N	N	R	N	R	N	N
	43	N	N	N	R	R	R	N	R	N	R	N	R		R	R	R	N	R	N	N	R	R	N	R
	47	R	N	R	N	N	R	N	N	N	N	R	N	N		R	R	R	N	R	N	R	R	R	R
	53	N	N	R	R	R	R	N	N	R	N	R	N	R	R		R	N	N	N	N	N	N	R	R
	59	R	R	R	N	N	R	R	N	R	N	N	R	N	N	R		N	N	R	N	R	N	N	N
	61	R	R	N	N	R	N	R	N	N	N	N	R	N	R	N	N		N	N	R	N	R	N	R
	67	N	N	N	N	N	R	R	R	R	N	R	N	N	R	N	R	N		R	R	N	R	R	N
	71	R	R	N	N	N	N	R	N	R	N	R	N	R	N	N	N	N	N		R	R	R	R	N
	73	R	N	N	N	N	N	R	R	N	N	R	R	N	N	N	N	R	R	R		R	N	R	R
	79	N	R	N	R	R	N	R	R	N	R	N	N	N	N	N	N	N	R	N	R		R	R	R
	83	R	N	R	R	N	R	N	R	R	R	R	R	N	N	N	R	R	N	N	N	N		N	N
	89	N	R	N	R	N	R	N	N	N	N	N	N	N	R	R	N	N	R	R	R	R	N		R
	97	R	N	N	R	N	N	N	N	N	R	N	N	R	R	R	N	R	N	N	R	R	N	R

На пример, $37$ је квадратни остатак по модулу $11$ (у табели четврти ред и једанаеста колона), јер је

$2^2-37=4-37=11\cdot (-3)$

дељиво са $11$. Поље R је обојено зеленом бојом, јер је $37\equiv 1(\mathrm{mod}4)$. Обрнуто, у једанаестом реду и четвртој колони, дакле на позицији $(37,11)$, поново се налази зелено поље, као што предвиђа квадратни закон реципроцитета.

Теорија простих бројева

Квадратни закон реципроцитета може се користити за директно истраживање простих бројева.

Делиоци Фермаових и Мерсенових бројева

Фермаови бројеви су дефинисани низом

$F_n:=2^{2^n}+1.$

Први Фермаови бројеви су експлицитно дати са

$F_0=3,F_1=5,F_2=17,F_3=257.$

Помоћу квадратног закона реципроцитета може се показати да сваки прост број $p$ који дели $F_n$ за $n\ge 2$ мора бити облика

$p=2^{n+2}k+1$

за неко $k\in \mathbb{N}$.

О доказу

Ово се може видети на следећи начин: због $p|F_n$ већ важи $2^{2^n}\equiv -1(\mathrm{mod}p)$, а након квадрирања обе стране $2^{2^{n+1}}\equiv 1(\mathrm{mod}p).$ Следи да је $p$-ред од $2$ у групи $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$ реда $\phi (p)=p-1$ тачно $2^{n+1}$, што према Лагранжовој теореми имплицира $2^{n+1}|(p-1)$. Због $n\ge 2$ је стога $p\equiv 1(\mathrm{mod}8)$. Помоћу другог допунског закона квадратног реципроцитета следи да је $2$ квадратни остатак по модулу $p$. Дакле, постоји $a\in \mathbb{Z}$ тако да је $a^2\equiv 2(\mathrm{mod}p)$, па је ред од $a$ чак једнак $2^{n+2}$. Тиме следи $2^{n+2}|(p-1)$.

Квадратни закон реципроцитета тиме даје снажно ограничење за могуће просте факторе ових бројева. Он представља једно од ретких познатих теоријских помагала за проналажење простих делилаца Фермаових бројева. На пример, сваки прост делилац $p$ броја

$F_5=2^{32}+1=\mathrm{4.294.967.297}$

је облика $p=128k+1$. Први бројеви са овим својством су

$129,257,513,641,\dots$

Од ових су само $F_3=257$ и $641$ заиста прости бројеви. Елементарним средствима може се показати да су два различита Фермаова броја узајамно прости, дакле немају заједничких простих фактора. Тиме се $257$ искључује као делилац броја $F_5$. Леонард Ојлер је био први који је препознао да је $641$ делилац броја $F_5$. Други прост фактор је $\mathrm{6.700.417}=128\cdot 52.347+1$, дакле

$F_5=641\cdot \mathrm{6.700.417.}$

Искључивањем свих простих бројева облика $128k+1$ испод $\sqrt{\mathrm{6.700.417}}\approx 2586$ као делилаца броја $\mathrm{6.700.417}$, брзо се увиђа да је $\mathrm{6.700.417}$ заиста поново прост. Ово би био највећи познати прост број у то време, и сматра се вероватним да је Ојлер знао за њега.

Квадратни закон реципроцитета може се на сличан начин искористити да се нешто каже о простим делиоцима Мерсенових бројева. То су бројеви

$M_p=2^p-1$

са простим бројевима $p$. Позната претпоставка каже да постоји бесконачно много простих бројева облика $M_p$, али то је до данас непознато. Помоћу $M_p$ су, међутим, неколико пута одређивани прости бројеви рекордне величине. Пример таквог Мерсеновог простог броја је $M_7=2^7-1=127.$ Насупрот томе, на пример, $M_{11}=2.047=23\cdot 89$ је сложен. Сада важи: ако је $p$ прост број такав да је $q:=2p+1$ поново прост, онда је $q$ тачно онда делилац броја $M_p$, када је $q\equiv \pm 1(\mathrm{mod}8)$. Кључни међукорак у доказу ове тврдње користи квадратни закон реципроцитета.

О доказу

Тврдње $q|M_p$ и $2^{\frac{q-1}{2}}\equiv 1(\mathrm{mod}q)$ су еквивалентне. Према Ојлеровом критеријуму, то је случај тачно онда када је $2$ квадратни остатак по модулу $q$. Из другог допунског закона сада следи тврдња.

Као закључак следи да ако је $p\equiv 3(\mathrm{mod}4)$ прост број такав да је $q:=2p+1$ поново прост, онда већ важи $q|M_p$. У овим случајевима, $M_p$ је дакле сложен. Као пример служи $p=11$, јер је $11\equiv 3(\mathrm{mod}4)$, а $2p+1=23$ је поново прост. Као што је горе виђено, $23$ дели број $M_{11}$.

Прост број $p$ такав да је $2p+1$ поново прост, назива се и прост број Софи Жермен.

Дирихлеова теорема о аритметичким прогресијама

Петер Густав Лежен Дирихле је показао да низови бројева као што су 1, 5, 9, 13, 17, 21, … или 7, 107, 207, 307, 407, … садрже бесконачно много простих бројева

Неки специјални случајеви Дирихлеове теореме о аритметичким прогресијама могу се директно доказати коришћењем квадратног закона реципроцитета. Дирихлеова теорема о аритметичким прогресијама пружа доказ о бесконачности простих бројева у одређеним аритметичким прогресијама. Аритметичке прогресије су низови бројева који увек имају исту разлику, као на пример

$1,5,9,13,17,21,\dots$

Она тврди да ако су разлика (горе $4$) и један члан низа (горе на пример $1$) узајамно прости, прогресија већ мора садржати бесконачно много простих бројева. Пошто су $4$ и $1$ узајамно прости, постоји, на пример, бесконачно много простих бројева унутар прогресије $1,5,9,13,17,21,\dots$. Први од ових простих бројева су

$5,13,17,29,37,41,\dots$

Ово је еквивалентно тврдњи да постоји бесконачно много простих бројева $p$ са својством $p\equiv 1(\mathrm{mod}4)$.

У случају разлика $1$ односно $2$, излагања су слична онима из Еуклидовог доказа да постоји бесконачно много (непарних) простих бројева. За разлике $d\in \{3,4,6\}$ може се делимично аргументовати квадратним остацима и законом реципроцитета.

• За $d=4$ треба размотрити само случајеве $p\equiv \pm 1(\mathrm{mod}4)$, пошто су бројеви са $n\equiv 0,2(\mathrm{mod}4)$ увек парни и стога дељиви са $2$. Док се за случај простих бројева са $p\equiv -1(\mathrm{mod}4)$ поново користи елементарни аргумент као код Еуклида, за просте бројеве облика $p\equiv 1(\mathrm{mod}4)$ (види горњи пример) посматрају се бројеви облика

$n_r:=(2\cdot p_1\cdot p_2\cdots p_r{)}^2+1.$

Притом су парови различитих непарних простих бројева $p_1,\dots ,p_r$ по претпоставци облика $p_j\equiv 1(\mathrm{mod}4)$, и аргументује се да увек постоји још један такав прост број $p_{r+1}$. Сваки прост фактор $p_{r+1}$ од $n_r$ по конструкцији није облика $2,p_1,\dots ,p_r$. Такође по конструкцији, број $-1$ је квадратни остатак по модулу $p_{r+1}$, дакле према првом допунском закону важи $\left(\frac{-1}{p_{r+1}}\right)=(-1{)}^{\frac{p_{r+1}-1}{2}}=1$, а тиме и $p_{r+1}\equiv 1(\mathrm{mod}4)$. Тиме коначна листа $p_1,\dots ,p_r$ тражених простих бројева није била потпуна, и мора постојати бесконачно много таквих бројева.

• За $d=6$ у случајевима $p\equiv -1(\mathrm{mod}6)$ може се поново аргументовати без квадратних остатака. У случајевима простих бројева облика $p\equiv 1(\mathrm{mod}6)$ прати се слична стратегија као код $p\equiv 1(\mathrm{mod}4)$. За парове различитих простих бројева $p_1,\dots ,p_r$ са жељеним својством посматра се број

$n_r:=(2\cdot p_1\cdot p_2\cdots p_r{)}^2+3$

Баш као и горе, сваки прост делилац $p_{r+1}$ броја $n_r$ није из листе $\{2,3,p_1,\dots ,p_r\}$. Осим тога, $-3$ је квадратни остатак по модулу $p_{r+1}$, дакле $\left(\frac{-3}{p_{r+1}}\right)=1$. Помоћу мултипликативности и квадратног закона реципроцитета следи

$1=\left(\frac{-3}{p_{r+1}}\right)=\left(\frac{-1}{p_{r+1}}\right)\left(\frac{3}{p_{r+1}}\right)=(-1{)}^{\frac{p-1}{2}}(-1{)}^{\frac{p-1}{2}\cdot \frac{3-1}{2}}\left(\frac{p_{r+1}}{3}\right)=\left(\frac{p_{r+1}}{3}\right).$

Дакле, $p_{r+1}\equiv 1(\mathrm{mod}3)$, а пошто је $p_{j+1}$ непаран, чак је $p_{j+1}\equiv 1(\mathrm{mod}6)$.

• Случајеви $d=3$ могу се извести из оних за $d=6$.

За сасвим опште разлике, елементарна машинерија није довољна. Сам Дирихле је за општи доказ користио новоразвијене технике из комплексне анализе.

Збирови квадрата

Коришћењем квадратног закона реципроцитета у неким случајевима може се показати под којим условима се прост број $p$ може написати у облику

$p=x^2+n{y}^2(x,y\in \mathbb{Z})$

за фиксно $n\in \mathbb{N}$. Ово је такође била покретачка снага теорије бројева у 18. веку, која је допринела његовом открићу. Случај $n=1$ води до питања који су непарни прости бројеви збир два квадрата. Може се показати да су то тачно прости бројеви облика $p\equiv 1(\mathrm{mod}4)$, дакле они који при дељењу са $4$ дају остатак $1$. Тако важи

$5=1^2+2^2,13=2^2+3^2,17=1^2+4^2,29=2^2+5^2,37=1^2+6^2,41=4^2+5^2,53=2^2+7^2,61=5^2+6^2.$

Овај резултат се данас углавном назива теоремом о два квадрата. Његов доказ на основу закона реципроцитета користи Туову лему. Са врло сличним средствима може се, на пример, обрадити и случај $x^2+3y^2$. Међутим, могу се третирати и специјалне „мешовите” квадратне форме, као што је $x^2+xy+41y^2$. Прост број $p≠163$ је тачно онда овог облика, ако је квадратни остатак по модулу $163$. У доказу је, између осталог, неопходно проверити да ли је $-163$ квадратни неостатак по модулу $q\in \{3,5,7,11,13,17,19,23\}$.

Решавање диофантских једначина

Диофантска једначина, названа по Диофанту из Александрије (око 250.), је полиномска једначина у најмање једној променљивој, при чему се појављују само целобројни коефицијенти. Пример је

$x^3-y^2=24.$

У контексту диофантских једначина увек се траже целобројна решења. Решењем Хилбертовог десетог проблема из 1970. године од стране Јурија Матијасевича познато је да не постоји општи поступак за одлучивање да ли је било која диофантска једначина решива или не. За неке једначине, међутим, може се помоћу квадратног закона реципроцитета показати да решење не може постојати. Ово се тиче, на пример, неких једначина у две променљиве типа

$b{x}^m+a{y}^2=k(b,a,k\in \mathbb{Z},m\in \mathbb{N}).$

Примери су нерешивост једначине $x^3-y^2=24$ (разлика кубног броја и квадратног броја никада није $24$) или $x^5-y^2=52$ (разлика петог степена и квадратног броја никада није $52$), над целим бројевима.

Аритметичка геометрија

Дубоко откриће теорије бројева било је да, како би се разумела алгебарска једначина (у више променљивих) у рационалним бројевима, може бити корисно посматрати је над коначним пољима. Притом се мисли на то да се она посматра у свим пољима ${𝔽}_p$ истовремено. Важан пример овог „локално-глобалног принципа” је теорема коју је Адријен-Мари Лежандр показао 1785. године:

За целе бројеве $a,b,c\in \mathbb{Z}$ различите од $0$, једначина $a{x}^2+b{y}^2+c{z}^2=0$ има рационално решење $(x,y,z)≠(0,0,0)$ тачно онда када су испуњени следећи услови: 1. $a,b$ и $c$ немају сви исти предзнак. 2. $-ab$ је квадратни остатак по модулу $c$, $-ac$ је квадратни остатак по модулу $b$ и $-bc$ је квадратни остатак по модулу $a$.

Веза са коначним пољима постаје, међутим, видљива тек кроз следећу, још општију, формулацију теореме Хасе-Минковског:

Једначина облика ${\sum }_{j,k=1}^n{a}_{j,k}{x}_j{x}_k=0$ са целим бројевима $a_{j,k}$ и променљивима $x_1,\dots ,x_n$ има нетривијално рационално решење тачно онда када је решива над реалним бројевима и конгруенција ${\sum }_{j,k=1}^n{a}_{j,k}{x}_j{x}_k\equiv 0(\mathrm{mod}p)$ за сваки прост број $p$ има решење.

Геометријски облик јединичне кружнице дефинисане алгебарском једначином $x^2+y^2=1$

Код овог линеарног пресликавања (типа смицања) црвена стрелица мења правац, док плава не мења. Плава стрелица је сопствени вектор овог смицања, јер не мења правац, а пошто јој дужина остаје непромењена, њена сопствена вредност је 1. $T_p$ сада чине бесконачан низ линеарних пресликавања, која, међутим, осим фактора растезања $a_p(Q)$, увек одржавају правац одређене „стрелице” $f_Q$ која припада једначини $Q$.

Пошто је $\mathbb{Q}$ бесконачно поље, може се десити да је скуп решења квадратне једначине бесконачан. Тако, на пример, једначина јединичне кружнице

$x^2+y^2=1$

има бесконачно много рационалних решења (свако такво решење одговара Питагориној тројци), на пример важи

${\left(\frac{3}{5}\right)}^2+{\left(\frac{4}{5}\right)}^2=\frac{9}{25}+\frac{16}{25}=\frac{9+16}{25}=\frac{25}{25}=1$

(а због $3^2+4^2=5^2$ је $(3,4,5)$ Питагорина тројка). Пошто су поља ${𝔽}_p$, међутим, сва коначна, једначина

$x^2+y^2=\bar{1}$

над ${𝔽}_p$ ће увек имати само коначан број решења. Фред Дајмонд и Џери Шурман указују да се квадратни закон реципроцитета може користити за тумачење броја решења по модулу $p$ једначине

$Q:x^2=d(d\in \mathbb{Z}\setminus \{0\})$

као сопствених вредности линеарних пресликавања

$T_p:V_Q\to V_Q$

између $ℂ$-векторског простора $V_Q$ који припада једначини $Q$. Прво, $Q$ над ${𝔽}_p$ има дискриминанту $D_Q=4d$, а једначина укупно $a_p(Q)+1$ решења, ако

$a_p(Q):=\left(\frac{4d}{p}\right).$

Као што је виђено у одељку о расподели квадратних остатака, величина $a_p(Q)$ због квадратног закона реципроцитета зависи искључиво од класе остатка $\bar{p}$ по модулу $4|d|$. Кључ је сада да се преко јединствене факторизације на просте бројеве $a_p(Q)$ прошири на произвољне природне аргументе $n=p_1^{c_1}{p}_2^{c_2}\cdots p_r^{c_r}$ помоћу правила

$a_n(Q):=a_{p_1}(Q{)}^{c_1}\cdot a_{p_2}(Q{)}^{c_2}\cdots a_{p_r}(Q{)}^{c_r}.$

Тиме су $a_n(Q)$ потпуно мултипликативни, дакле увек важи $a_{mn}(Q)=a_m(Q)a_n(Q)$. Као векторски простор $V_Q$ може се сада дефинисати колекција свих пресликавања из групе примитивних остатака по модулу $4|d|$ у комплексне бројеве, дакле

$V_Q:=\{f:(\mathbb{Z}/4|d|\mathbb{Z}{)}^{\times }\to ℂ\}.$

Пошто је група $(\mathbb{Z}/4|d|\mathbb{Z}{)}^{\times }$ коначна, $V_Q$ је коначнодимензионалан. На $V_Q$ се сада може посматрати систем линеарних пресликавања $T_p$ (са $p$ прост број):

$(T_{p}f)(\bar{n}):=\{\begin{array}{cc}f(\overline{pn}),& amp;4|d|\equiv ̸0(\mathrm{mod}p),\\ 0,& amp;\text{иначе}.\end{array}$

Притом се редукције $\bar{n}$ и $\overline{pn}$ разумеју по модулу $4|d|$. Пошто се $a_p(Q)$ жели схватити као симултане сопствене вредности, мора се још пронаћи одговарајућа функција $f_Q\in V_Q$. Према квадратном закону реципроцитета, избор $f_Q(\bar{n}):=a_n(Q)$ је добро дефинисан. Са мултипликативношћу $a_n(Q)$ следи

$(T_p{f}_Q)(n)=a_{pn}(Q)=a_p(Q)a_n(Q)=a_p(Q)f_Q(n),$ дакле $T_p{f}_Q=a_p(Q)f_Q.$

Дакле, $f_Q\in V_Q$ је сопствени вектор од $T_p$ са сопственом вредношћу $a_p(Q)$.

Иако локално-глобални принцип за кубне једначине више није тачан, понашање бројева решења као сопствених вредности, индуковано квадратним законом реципроцитета, може се уопштити на неке кубне криве. Тиме се посебно мисли на криве облика

$E:y^2=x^3-ax-b(a,b\in \mathbb{Z},D_E=a^3-27b^2≠0)$

Мисли се на криве овог облика. Оне се називају и елиптичким кривама и од централног су значаја у теорији бројева. Ако се овде броје решења $|E_p|$ криве над пољима ${𝔽}_p$, дакле парови $(x,y)\in {𝔽}_p\times {𝔽}_p$ са $y^2=x^3-\bar{a}x-\bar{b}$, налази се да бројеви

$a_p(E):=p-|E_p|$

поново наступају као систем симултаних сопствених вредности линеарних пресликавања $T_p:V_E\to V_E$ између коначнодимензионалних $ℂ$-векторских простора $V_E$ који зависе само од криве $E$. Притом се ради о $V_E$ као просторима модуларних форми, а $T_p$ представљају Хекеове операторе. Ово је верзија теореме о модуларности, коју су 1995. године доказали Ендру Вајлс и Ричард Тејлор, а њен изузетно компликован доказ спада у велике математичке напретке 20. века. Значајно је да се Лежандров симбол у овој варијанти „замењује” модуларним формама, које се тиме појављују као „виши карактери”. Тиме се квадратни закон реципроцитета односи на „први ступањ”, док модуларне форме представљају „други ступањ”. О „трећем ступњу” и даље, до данас, готово ништа није познато. Ова питања су, међутим, у оквиру Ленглендсовог програма предмет интензивног истраживања.

Докази

Гаусова формулација квадратног закона реципроцитета. У његовој нотацији, $aRb$ значи да је $a$ квадратни остатак по модулу $b$, а аналогно за неостатке са $aNb$.

У 19. и 20. веку пронађени су бројни различити докази за квадратни закон реципроцитета. Сам Гаус је представио најмање осам различитих доказа. Његов први доказ је изведен преко веома тешког и компликованог аргумента помоћу потпуне индукције. Овај доказ је касније поједноставио Петер Густав Лежен Дирихле у својим Предавањима о теорији бројева (објављеним 1863). Он подсећа на Лежандров покушај доказа, јер такође захтева конструкцију помоћног простог броја. Сложеност Гаусовог аргумента произилази из потребе да се докаже постојање овог простог броја, а технички прорачуни које је Гаус морао да изведе довели су до тога да је његов аргумент дуги низ година био мало запажен. Његови прорачуни су се, међутим, показали корисним у развоју алгебарске К-теорије 1970-их година; заиста, доказ квадратне реципроцитета може се извести из одређених резултата К-теорије рационалних бројева. Гаусов други доказ се такође појавио у Disquisitiones и користи теорију родова квадратних форми, коју су иницирали Лагранж и он. Ова омогућава класификацију форми, која је уско повезана са Лагранжовом класификацијом квадратних форми помоћу унимодуларних супституција. Притом се квадратна форма $q(x,y)$ супституцијом променљивих $q(ax+by,cx+dy)$ преводи у другу форму, која у суштини има иста својства као прва форма. Главна тачка аргумента овде је доказ неједнакости за број родова за форме. Овај доказ се добро може извести у модерном стручном језику алгебарске теорије бројева, наиме преко еквиваленције идеала у квадратним бројним пољима.

До сада је објављено више од 300 доказа. Међутим, ови докази нису сви потпуно различити. Неки се разликују само у неколико детаља. Нови докази се проналазе и у данашње време. На пример, Франц Лемермајер је 2022. године објавио један такав, користећи Гаусову лему и Ермитов идентитет.

У наставку се разматра избор доказа квадратног закона реципроцитета. Скициране су идеје доказа и дати су важни кораци. Детаљнији прикази налазе се у литератури.

Преко Гаусове леме

Гаусова лема се користи у неким доказима квадратног закона реципроцитета. Између осталог, коришћена је у Гаусовом петом доказу. Ради се о методи за израчунавање Лежандровог симбола. Да би се ово разумело, прво се посматра „прва половина” класа остатака по модулу непарног простог броја $p$:

$H_p:=\{\bar{1},\bar{2},\dots ,\overline{\frac{p-1}{2}}\}.$

Свака класа остатка $\bar{a}≠0$ сада има облик $\bar{a}=\epsilon \cdot \bar{h}$ са предзнаком $\epsilon \in \{-1,1\}$ и $\bar{h}\in H_p$, обоје јединствено одређено. Сада се одређује низ предзнака ${\epsilon }_j$ који припадају $\bar{a}$ преко

$\bar{1}\cdot \bar{a}={\epsilon }_1(a)\cdot \overline{h_1(a)},\bar{2}\cdot \bar{a}={\epsilon }_2(a)\cdot \overline{h_2(a)},\cdots ,\overline{\frac{p-1}{2}}\cdot \bar{a}={\epsilon }_{\frac{p-1}{2}}(a)\cdot \overline{h_{\frac{p-1}{2}}(a)},$

са $\overline{h_1(a)},\dots ,\overline{h_{\frac{p-1}{2}}(a)}\in H_p$. Гаусова лема тврди да

$\left(\frac{a}{p}\right)=\prod _{j=1}^{\frac{p-1}{2}}{\epsilon }_j(a)={\epsilon }_1(a)\cdot {\epsilon }_2(a)\cdots {\epsilon }_{\frac{p-1}{2}}(a).$

Готхолд Ајзенштајн

Ајзенштајнов доказ користи чињеницу да је синус непарна и истовремено $2\pi$-периодична функција

Централно средство у доказу Гаусове леме је Ојлеров критеријум, јер се за $p\ge 3$ тада само треба показати

$a^{\frac{p-1}{2}}\equiv \prod _{j=1}^{\frac{p-1}{2}}{\epsilon }_j(a)={\epsilon }_1(a)\cdot {\epsilon }_2(a)\cdots {\epsilon }_{\frac{p-1}{2}}(a)(\mathrm{mod}p)$

Трик у једној методи доказа квадратног закона реципроцитета је да се предзнаци ${\epsilon }_j$ експлицитније изразе: прво се пише $j\cdot a={\epsilon }_j(a)\cdot h_j(a)+e_j\cdot p$ са $1\le h_j(a)\le \frac{p-1}{2}$ и $e_j\in \mathbb{Z}$. Разликовањем случајева се затим налази

${\epsilon }_j(a)=(-1{)}^{\left[\frac{2aj}{p}\right]},$

где $\left[x\right]$ означава целобројни део од $x\in ℝ$. Према Гаусовој леми је дакле

$\left(\frac{a}{p}\right)=(-1{)}^{\sum _{j=1}^{\frac{p-1}{2}}\left[\frac{2aj}{p}\right]}.$

Ова формула је полазна тачка за низ корака трансформације, који заједно са бројањем одређених целобројних тачака у правоугаонику $ℛ\subset {\mathbb{Z}}^2$ дефинисаном простим бројевима $p,q$ воде до жељеног резултата. Гаусова лема је, међутим, такође помоћно средство у даљим доказима за квадратни закон реципроцитета. Један од њих је чувени доказ Готхолда Ајзенштајна из 1845. године, објављен у часопису Crelle's Journal. Овај доказ почиње са тригонометријским идентитетом који важи за непарно $m>1$

$\frac{\sin (mx)}{\sin (x)}\equiv (-4{)}^{\frac{m-1}{2}}\prod _{j=1}^{\frac{m-1}{2}}(\sin (x{)}^2-\sin {\left(\frac{2\pi j}{m}\right)}^2).$

Притом $\sin (x)$ означава вредност синусне функције у тачки $x$, а горња формула важи за све $x\in ℝ$ (на местима $x\in \pi \mathbb{Z}$ постоје отклоњиви сингуларитети, што омогућава непрекидно продужење). Овај идентитет се може елементарно показати помоћу поређења коефицијената између полинома и употребом Ојлерове формуле $e^{i\varphi }=\cos (\varphi )+i\sin (\varphi )$. Пошто је синус непарна функција, дакле увек важи $\sin (\pm x)=\pm \sin (x)$, али и $2\pi$-периодична функција, због дефиниције предзнака ${\epsilon }_j(a)$ имамо

$\sin \left(\frac{2\pi }{p}aj\right)=\sin (\frac{2\pi }{p}{\epsilon }_j(a)h_j(a))={\epsilon }_j(a)\sin (\frac{2\pi }{p}{h}_j(a)),(h_j(a)\in H_p).$

Тиме важи за непарне просте бројеве $p≠q$:

$\left(\frac{q}{p}\right)\stackrel{\text{Гаусова лема}}{=}\prod _{j\in H_p}\frac{\sin \left(\frac{2\pi qj}{p}\right)}{\sin \left(\frac{2\pi j}{p}\right)}\stackrel{\text{Триг. идентитет}}{=}\prod _{j\in H_p}(-4{)}^{\frac{q-1}{2}}\prod _{k\in H_q}(\sin {\left(\frac{2\pi j}{p}\right)}^2-\sin {\left(\frac{2\pi k}{q}\right)}^2)=(-4{)}^{\frac{p-1}{2}\frac{q-1}{2}}\prod _{\genfrac{}{}{0ex}{}{j\in H_p}{k\in H_q}}(\sin {\left(\frac{2\pi j}{p}\right)}^2-\sin {\left(\frac{2\pi k}{q}\right)}^2).$

Кључна тачка је сада „симетрија до на предзнак $(-1{)}^{|H_p||H_q|}=(-1{)}^{\frac{p-1}{2}\frac{q-1}{2}}$” која се појављује на десној страни. Заиста, заменом простих бројева $p,q$ важи потпуно аналогно

$\left(\frac{p}{q}\right)=(-4{)}^{\frac{q-1}{2}\frac{p-1}{2}}\prod _{\genfrac{}{}{0ex}{}{j\in H_p}{k\in H_q}}(\sin {\left(\frac{2\pi k}{q}\right)}^2-\sin {\left(\frac{2\pi j}{p}\right)}^2)=(-1{)}^{\frac{p-1}{2}\frac{q-1}{2}}(-4{)}^{\frac{p-1}{2}\frac{q-1}{2}}\prod _{\genfrac{}{}{0ex}{}{j\in H_p}{k\in H_q}}(\sin {\left(\frac{2\pi j}{p}\right)}^2-\sin {\left(\frac{2\pi k}{q}\right)}^2)=(-1{)}^{\frac{p-1}{2}\frac{q-1}{2}}\left(\frac{q}{p}\right),$

јер је множење комутативно. Значајно за овај доказ је да се он може прилагодити и за више законе реципроцитета, тако што се синус замењује елиптичким функцијама. На овај начин је Ајзенштајн доказао кубни и биквадратни закон реципроцитета. Теоретичар бројева Ернст Едуард Кумер је о томе коментарисао:

Аналитички доказ

Постоји могућност да се квадратни закон реципроцитета докаже средствима из анализе. У анализи су у првом плану својства функција (као што су непрекидност и диференцијабилност). За доказ се разматра одређена математичка функција, наиме Јакобијева тета-функција, названа по Карлу Густаву Јакобу Јакобију. Она има две независне променљиве, при чему једна променљива $t$ мора бити изабрана из интервала $(0,\mathrm{\infty })$. Да би се показао реципроцитет, трик је да се ова функција испита на два различита начина у граничном процесу $t\to 0^{+}$. Након тога се појављују два различито изгледајућа израза за исту формулу. „Поређењем” тих израза се на крају може извести закон реципроцитета.

Детаљи

Доказ помоћу техника из анализе користи понашање Јакобијеве тета-функције $\vartheta (z,\tau ):=\sum _{n=-\mathrm{\infty }}^{\mathrm{\infty }}{e}^{\pi i{n}^2\tau +2\pi inz}$ у близини тачке $\tau =0$. Тета-функција представља холоморфну функцију у целом $ℂ\times ℍ$, где је $ℍ=\{\tau \in ℂ:\mathrm{I}\mathrm{m}(\tau )>0\}$ горња полураван комплексних бројева. Трик је да се асимптотско понашање израза $\vartheta (0,it+\frac{2K}{N})=\sum _{n=-\mathrm{\infty }}^{\mathrm{\infty }}{e}^{\pi i{n}^2(it+\frac{2K}{N})}$ за $t\to 0^{+}$ одреди на два различита начина. Притом се одлучујуће користе модуларне трансформационе формуле тета-функције. На овај начин се налази Ландсберг-Шар формула, која важи за све природне бројеве $N$ и $K$: $\frac{1}{\sqrt{N}}\sum _{m=1}^N{e}^{\frac{2\pi i{m}^{2}K}{N}}=\frac{e^{\frac{\pi i}{4}}}{\sqrt{2K}}\sum _{n=1}^{2K}{e}^{-\frac{\pi i{n}^{2}N}{4K}}.$ Ова формула се може користити за доказивање формуле која се тиче квадратне Гаусове суме: $\sum _{n=1}^N{e}^{\frac{2\pi i{n}^2}{N}}=\sqrt{N}{i}^{\frac{(N-1{)}^2}{4}}=\{\begin{array}{cc}\sqrt{N}& amp;N\equiv 1(\mathrm{mod}4),\\ \sqrt{N}i& amp;N\equiv 3(\mathrm{mod}4),\end{array}$ Одређивање тачног предзнака овог израза није тривијално. Да у оба случаја стоји знак плус, Гаус је претпоставио у мају 1801. године, али је то доказао тек 1805. Након тога, производ $𝒢(q;p)𝒢(p;q)$ Гаусових сума које одговарају Лежандровом симболу $𝒢(q;p):=\sum _{k=1}^p\left(\frac{k}{p}\right)e^{\frac{2\pi ikq}{p}}=\sum _{k=1}^p{e}^{\frac{2\pi i{k}^{2}q}{p}}$ и сходно томе $𝒢(p;q)$ може се израчунати на два различита начина: једном се добија преко чињенице да је Лежандров симбол по модулу $p$ и $q$ примитивни Дирихлеов карактер, $𝒢(q;p)𝒢(p;q)=\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)𝒢(1;p)𝒢(1;q)=\sqrt{pq}{i}^{\frac{(p-1{)}^2+(q-1{)}^2}{4}}.$ С друге стране, директним множењем важи $𝒢(q;p)𝒢(p;q)=\sum _{m=1}^p\sum _{n=1}^q{e}^{\frac{2\pi i(mq+np{)}^2}{pq}}=\sum _{n=1}^{pq}{e}^{\frac{2\pi i{n}^2}{pq}}=\sqrt{pq}{i}^{\frac{(pq-1{)}^2}{4}}.$ Поређењем се добија $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=i^{\frac{(pq-1{)}^2-(p-1{)}^2-(q-1{)}^2}{4}}=i^{\frac{(p-1)(q-1)(pq+p+q-1)}{4}},$ а предзнак на десној страни је тачно $(-1{)}^{\frac{p-1}{2}\frac{q-1}{2}}$.

Овај доказ потиче од Г. Ландсберга из 1893. године (објављен у Crelle's Journal). Математичар Ерих Хеке је успео да поново преузме идеју и са вишедимензионалним тета-функцијама докаже закон реципроцитета у бројним пољима. Хеке је о томе написао: „Чињеница је да прецизније познавање понашања аналитичке функције у близини њених сингуларних тачака представља извор аритметичких теорема”.

Комбинаторни доказ

Јегор Иванович Золотарјов

Лема Золотарјова успоставља везу између Лежандровог симбола и знака пермутације. Ако је $a$ цео број и $p$ непаран прост број који не дели $a$, онда пресликавање

${\pi }_{a,p}:{𝔽}_p^{\times }\to {𝔽}_p^{\times },{\pi }_{a,p}(\overline{k}):=\overline{ak}$

представља пермутацију елемената групе примитивних остатака ${𝔽}_p^{\times }$ (бројева од $1$ до $p-1$). Лема Золотарјова сада каже да је Лежандров симбол $\left(\frac{a}{p}\right)$ једнак знаку ове пермутације, то јест,

$\left(\frac{a}{p}\right)=\mathrm{sgn}({\pi }_{a,p})$.

Лема омогућава једноставан доказ квадратног закона реципроцитета. Названа је по руском математичару Јегору Ивановичу Золотарјову, који је лему и овај доказ представио 1872. године. Фердинанд Георг Фробенијус је ове резултате уопштио 1914. године за Јакобијев симбол.

Допунски закони

Први допунски закон $\left(\frac{-1}{p}\right)=(-1{)}^{\frac{p-1}{2}}$ за просте бројеве $p\ge 3$ је непосредна последица тврдње да је $x$ тачно онда квадратни остатак по модулу $p$, ако је $x^{\frac{p-1}{2}}\equiv 1(\mathrm{mod}p)$, види Ојлеров критеријум.

За други допунски закон може се поступити на следећи начин. Поново се за просте бројеве $p\ge 3$ посматрају конгруенције

$\begin{array}{cc}p-1& amp;\equiv 1(-1{)}^1(\mathrm{mod}p)\\ 2& amp;\equiv 2(-1{)}^2(\mathrm{mod}p)\\ p-3& amp;\equiv 3(-1{)}^3(\mathrm{mod}p)\\ & amp;⋮\\ k& amp;\equiv \frac{p-1}{2}(-1{)}^{\frac{p-1}{2}}(\mathrm{mod}p)\end{array}$

са $k=2\cdot \lfloor \frac{p+1}{4}\rfloor \in \{\frac{p-1}{2},\frac{p+1}{2}\}=\{\frac{p-1}{2},p-\frac{p-1}{2}\}$ (тако да на левим странама стоје сви парни бројеви између $1$ и $p$). Оне су очигледне. Из тога одмах следи

$2\cdot 4\cdot 6\cdots (p-1)\equiv \left(\frac{p-1}{2}\right)!(-1{)}^{1+2+3+\cdots +\frac{p-1}{2}}=\left(\frac{p-1}{2}\right)!(-1{)}^{\frac{p^2-1}{8}}(\mathrm{mod}p)$,

дакле (јер је $\left(\frac{p-1}{2}\right)!$ узајамно прост са $p$) $2^{\frac{p-1}{2}}\equiv (-1{)}^{\frac{p^2-1}{8}}(\mathrm{mod}p)$. Сада се поново може аргументовати Ојлеровим критеријумом.

Уопштења

Реципроцитет код Јакобијевог симбола

Карл Густав Јакоби

Лежандров симбол се може уопштити на различите начине. Један од очигледних начина је да се за модуо дозволе и сложени бројеви. Ако је факторизација на просте бројеве од $n=p_1^{{\nu }_1}\cdot p_2^{{\nu }_2}\cdots p_k^{{\nu }_k}$ са паровима различитих $p_{\ell }$, онда се Јакобијев симбол дефинише као

$\left(\frac{a}{n}\right):={\left(\frac{a}{p_1}\right)}^{{\nu }_1}\cdots {\left(\frac{a}{p_k}\right)}^{{\nu }_k}.$

Пример је:

$\left(\frac{14}{15}\right)=\left(\frac{14}{3}\right)\left(\frac{14}{5}\right).$

Треба имати на уму да су Лежандров и Јакобијев симбол идентични за прост $n$. Са становишта теорије бројева, код Јакобијевог симбола је потребан опрез. Ако је $(\frac{a}{n})=-1$, онда конгруенција

$x^2\equiv a(\mathrm{mod}n)$

дефинитивно није решива. Међутим, $(\frac{a}{n})=1$ не гарантује постојање решења ако $n$ није прост број. Међутим, и даље важи закон реципроцитета: за све непарне целе бројеве $m,n$ веће од $1$ важи

$\left(\frac{m}{n}\right)=(-1{)}^{\frac{(m-1)}{2}\frac{(n-1)}{2}}\left(\frac{n}{m}\right).$

Такође, за непарно $n$ важе и допунски закони:

• $\left(\frac{-1}{n}\right)=(-1{)}^{\frac{n-1}{2}}=\{\begin{array}{cc}1,& amp;n\equiv 1(\mathrm{mod}4)\\ -1,& amp;n\equiv 3(\mathrm{mod}4),\end{array}$
• $\left(\frac{2}{n}\right)=(-1{)}^{\frac{n^2-1}{8}}=\{\begin{array}{cc}1,& amp;n\equiv \pm 1(\mathrm{mod}8)\\ -1,& amp;n\equiv \pm 3(\mathrm{mod}8).\end{array}$

Кубни и биквадратни закон реципроцитета

Док се цели бројеви приказују као тачке на реалној оси (бројевна права), Ајзенштајнови бројеви се појављују као тачке решетке у комплексној равни.

Слично као што се квадратни закон реципроцитета односи на квадрате, кубни закон реципроцитета се бави трећим степеном. За његову формулацију, међутим, неопходно је напустити домен целих бројева $\mathbb{Z}$. Он се проширује вредношћу

$\omega =e^{\frac{2\pi i}{3}}=-\frac{1}{2}+\frac{\sqrt{3}}{2}i$ (са имагинарном јединицом $i$),

дакле, трећим кореном јединице. Стога је ${\omega }^3=1$, а због $\omega ≠1$ важи и ${\omega }^2+\omega +1=0$. Експлицитно важи

$\mathbb{Z}[\omega ]=\{a+b\omega |a,b\in \mathbb{Z}\}$

а бројеви $\mathbb{Z}[\omega ]$ се називају Ајзенштајнови бројеви. Може се показати да постоји аналогон за просте бројеve у $\mathbb{Z}[\omega ]$. Позадина тога је да $\mathbb{Z}[\omega ]$ има веома сличне особине као цели бројеви, јер је $\mathbb{Z}[\omega ]$ као и $\mathbb{Z}$ Еуклидов домен, па је дељење са остатком могуће и у Ајзенштајновим бројевима. Кључ за формулацију кубног закона реципроцитета је карактеризација „простих бројева“ у $\mathbb{Z}[\omega ]$. Пошто се појам простог броја односи на целе бројеве, у овом општијем контексту говори се о простим елементима (прстена $\mathbb{Z}[\omega ]$). У Еуклидовим прстеновима сваки број има, до на редослед фактора и јединице (дакле, бројеве којима се у прстену увек може делити, као što су $\pm 1$ у $\mathbb{Z}$), јединствену факторизацију на просте елементе. Полазна тачка је пресликавање норме

$N_{\mathbb{Z}[\omega ]}:\mathbb{Z}[\omega ]\to {\mathbb{N}}_0,N_{\mathbb{Z}[\omega ]}(a+b\omega ):=a^2-ab+b^2.$

„Први“ прости елементи међу Ајзенштајновим бројевима у комплексној равни. Ротациона симетрија за 60° следи из постојања шест јединица у $\mathbb{Z}[\omega ]$.

Она је мултипликативна, дакле испуњава $N_{\mathbb{Z}[\omega ]}(xy)=N_{\mathbb{Z}[\omega ]}(x)N_{\mathbb{Z}[\omega ]}(y)$ за све $x,y\in \mathbb{Z}[\omega ]$. Пресликавање норме пресликава Ајзенштајнове бројеве $a+b\omega$ на лакше разумљиве ненегативне целе бројеве $a^2-ab+b^2$ и тиме помаже у њиховом истраживању. Тако је, на пример, сваки елемент $\alpha$ из $\mathbb{Z}[\omega ]$ прост елемент ако је његова норма $N_{\mathbb{Z}[\omega ]}(\alpha )$ прост број, али postoje и прости елементи са сложеном нормом. Наиме, ако је $p$ прост број, тада је $N_{\mathbb{Z}[\omega ]}(p)=p^2$ и важи:

1. $p=3$ није прост елемент у $\mathbb{Z}[\omega ]$, већ је разложив: $3=-{\omega }^2(1-\omega {)}^2$. Пошто је $\{\pm 1,\pm \omega ,\pm {\omega }^2\}$ скуп шест јединица од $\mathbb{Z}[\omega ]$, $3$ је асоциран са квадратом простог елемента $1-\omega$. Два елемента се називају асоцираним ако се разликују само за мултипликативну јединицу. На пример, $2$ и $-2$ су асоцирани у $\mathbb{Z}$, јер је тамо $-1$ јединица.
2. Сваки $p\equiv 1(\mathrm{mod}3)$ није прост елемент, већ је разложив: $p=\pi \bar{\pi }$ са два неасоцирана проста елемента $\pi$ и $\bar{\pi }$ из $\mathbb{Z}[\omega ]$ исте норме $p$. $p$ дакле није ни прост елемент у $\mathbb{Z}[\omega ]$ нити асоциран са квадратом простог елемента. На пример, у $\mathbb{Z}[\omega ]$ важи: $7=(2-\omega )(3+\omega )$.
3. Сваки $p\equiv 2(\mathrm{mod}3)$ „остаје“ прост елемент у $\mathbb{Z}[\omega ]$ (треба имати у виду да $\mathbb{Z}[\omega ]$ садржи целе бројеве као подскуп). На пример, $5$ у $\mathbb{Z}[\omega ]$ нема других делилаца осим шест елемената асоцираних са $1$ и шест елемената асоцираних са самим $5$.

Слично као у целим бројевима, помоћу дељења са остатком из $\mathbb{Z}[\omega ]$ и простог елемента $\pi$ може се конструисати коначно поље са ознаком $\mathbb{Z}[\omega ]/\pi \mathbb{Z}[\omega ]$. Два елемента $\alpha$ и $\beta$ даље испуњавају

$\alpha \equiv \beta (\mathrm{mod}\pi ),$

ако је $\alpha -\beta \in \pi \mathbb{Z}[\pi ]$, дакле ако је $\alpha -\beta$ дељиво са $\pi$. Пошто група јединица $(\mathbb{Z}[\omega ]/\pi \mathbb{Z}[\omega ]{)}^{\times }$ има тачно $N_{\mathbb{Z}[\omega ]}(\pi )-1$ елемената, Мала Фермаова теорема се може проширити на

${\alpha }^{N_{\mathbb{Z}[\omega ]}(\pi )-1}\equiv 1(\mathrm{mod}\pi )(\alpha \notin \pi \mathbb{Z}[\omega ])$.

Ово истовремено мотивише кубну генерализацију Ојлеровог критеријума на

${\alpha }^{\frac{N_{\mathbb{Z}[\omega ]}(\pi )-1}{3}}\equiv 1,\omega ,{\omega }^2(\mathrm{mod}\pi ).$

Јединица којој је ${\alpha }^{\frac{N_{\mathbb{Z}[\omega ]}(\pi )-1}{3}}$ конгруентно по модулу $\pi$ је због $x^3-1\equiv (x-1)(x-\omega )(x-{\omega }^2)(\mathrm{mod}\pi )$ јединствено одређена, јер је $\mathbb{Z}[\omega ]/\pi \mathbb{Z}[\omega ]$ поље. Управо та одговарајућа јединица је вредност (кубног) Лежандровог симбола

${\alpha }^{\frac{N_{\mathbb{Z}[\omega ]}(\pi )-1}{3}}\equiv {\left(\frac{\alpha }{\pi }\right)}_3(\mathrm{mod}\pi ).$

Гаусови цели бројеви као тачке решетке у комплексној равни

За примарне просте елементе $\pi \equiv \pm 1(\mathrm{mod}3)$ сада се може формулисати кубни реципроцитет: За примарне просте елементе $\pi$ и $\theta$ у $\mathbb{Z}[\omega ]$ важи

${\left(\frac{\pi }{\theta }\right)}_3={\left(\frac{\theta }{\pi }\right)}_3.$

За формулацију биквадратног закона реципроцитета мора се поступити аналогно кубном закону реципроцитета. Овог пута је релевантан прстен $\mathbb{Z}[i]$ Гаусових целих бројева. Одговарајуће пресликавање норме, које служи за одређивање простих елемената, јесте $N_{\mathbb{Z}[i]}(a+bi):=a^2+b^2$. Исписано, оно каже да за све примарне просте елементе $\pi ,\theta \equiv 1(\mathrm{mod}2+2i)$ из $\mathbb{Z}[i]$ важи идентитет

${\left(\frac{\theta }{\pi }\right)}_4={\left(\frac{\pi }{\theta }\right)}_4(-1{)}^{\frac{(N_{\mathbb{Z}[i]}(\theta )-1)(N_{\mathbb{Z}[i]}(\pi )-1)}{16}}$.

Артинов закон реципроцитета

Емил Артин

Велико достигнуће теорије бројева 20. века било је уједињење свих до тада познатих закона реципроцитета помоћu нових концепата и средстава апстракције. То је успело алгебричару Емилу Артину у низу радова из 1924, 1927. и 1930. године. Да би се разумела његова изјава, потребно је извесно знање из алгебарске теорије бројева. У његовој верзији о глобалним пољима он гласи овако: Ако је $K$ глобално поље, на пример $K=\mathbb{Q}$, а $L/K$ Абелова екстензија, Лежандров симбол се може генерализовати са овим подацима. Ако прост идеал $𝔭\subset {𝒪}_K$ (прстена целих бројева $K$) није разгранат у $L$, а $𝔓\subset {𝒪}_L$ је прост идеал који садржи $𝔭$, онда постоји јединствено одређен елемент $\sigma \in \mathrm{G}\mathrm{a}\mathrm{l}(L/K)$ (у Галоаовој групи у односу на проширење $L/K$), тако да за све $\alpha \in {𝒪}_L$ већ важи

$\sigma (\alpha )\equiv {\alpha }^{N(𝔭)}(\mathrm{mod}𝔓)$

где $N(𝔭)$ означава кардиналност количничког поља ${𝒪}_K/𝔭$. Тако добијени аутоморфизам поља $\sigma \in \mathrm{G}\mathrm{a}\mathrm{l}(L/K)$ индукује Артинов симбол путем дефиниције

$\left(\frac{L/K}{𝔭}\right)(\alpha )\equiv {\alpha }^{N(𝔭)}(\mathrm{mod}𝔓).$

Ово сада путем „линеарности“ даје пресликавање (Артиново пресликавање за $L/K$ и $𝔪$)

$\left(\frac{L/K}{\cdot }\right):I_K(𝔪)\to \mathrm{G}\mathrm{a}\mathrm{l}(L/K),$

где $I_K(𝔪)$ означава групу разломљених идеала над $K$ који су узајамно прости са модулом $𝔪$ који припада проширењу $L/K$, пошто сваки $𝔞\in I_K(𝔪)$ има јединствену факторизацију

$𝔞={𝔭}_1^{r_1}\cdot {𝔭}_2^{r_2}\cdot \dots \cdot {𝔭}_{\ell }^{r_{\ell }}(r_j\in \mathbb{Z})$

на просте идеале. Модул притом мора бити дељив свим разгранатим простим идеалима. Може се показати да је ово Артиново пресликавање сурјективни хомоморфизам група. Артинов закон реципроцитета сада израчунава језгро овог пресликавања, и тиме према теореми о хомоморфизму успоставља изоморфизам група. Ово је производ норми $N_{L/K}(I_L(𝔪))$ разломљених идеала у $L$ који су узајамно прости са $𝔪$ и подгрупе $P_{K,1}(𝔪)$ генерисане главним идеалима $\alpha {𝒪}_K$ ($\alpha \in {𝒪}_K$), при чему је $\alpha \equiv 1(\mathrm{mod}{𝔪}_0)$ и $\sigma (\alpha )>0$ за све реалне бесконачне просте тачке $\sigma$ које деле ${𝔪}_{\mathrm{\infty }}$ (модул је формални производ $𝔪={𝔪}_0{𝔪}_{\mathrm{\infty }}$). Ово језгро се такође назива група идеала дефинисана mod $𝔪$, која припада проширењу $L/K$. Количник изоморфан Галоаовој групи понекад се назива и генерализована група класа идеала. Галоаова група се Артиновим законом реципроцитета дакле реализује као таква. Артинов симбол стога, пошто је $P_{K,1}(𝔪)$ део језгра, зависи од $𝔭$ само до на множење са $\alpha \equiv 1(\mathrm{mod}𝔪)$. Овде се поново препознаје Ојлерова формулација квадратног закона реципроцитета (види одељак Историја). Из Артиновог закона реципроцитета може се извести квадратни закон реципроцитета на следеći начин: Прво се, узимајући у обзир 1. допунски закон, може написати у облику

$\left(\frac{p^{\ast }}{q}\right)=\left(\frac{q}{p}\right)$

са $p^{\ast }:=(-1{)}^{\frac{p-1}{2}}p$. Први корак је сада проучавање проширења $\mathbb{Q}\subset \mathbb{Q}(\sqrt{p^{\ast }})$. $\mathrm{G}\mathrm{a}\mathrm{l}(\mathbb{Q}({\zeta }_p)/\mathbb{Q})$ је генерализована група класа идеала у односу на модул $p\mathrm{\infty }$, што се односи и на свако међупоље $\mathbb{Q}\subset K\subset \mathbb{Q}({\zeta }_p)$. Пошто је $\mathrm{G}\mathrm{a}\mathrm{l}(\mathbb{Q}({\zeta }_p)/\mathbb{Q})\cong (\mathbb{Z}/p\mathbb{Z}{)}^{\times }$ циклична група реда $p-1$, постоји јединствено одређено међупоље $\mathbb{Q}\subset K\subset \mathbb{Q}({\zeta }_p)$ које је квадратно проширење од $\mathbb{Q}$. Тада је $\mathrm{G}\mathrm{a}\mathrm{l}(K/\mathbb{Q})$ већ генерализована група класа идеала за $p\mathrm{\infty }$, што значи да је $p$ једина коначна проста тачка која је разграната над $K/\mathbb{Q}$. Ако напишемо $K=\mathbb{Q}(\sqrt{m})$, $m$ без квадрата, може се показати да је $m=p^{\ast }$ и последично $K=\mathbb{Q}(\sqrt{p^{\ast }})$. Следи

$P_{p\mathrm{\infty },1}\subset \mathrm{K}\mathrm{e}\mathrm{r}\mathrm{n}\left(\frac{\mathbb{Q}(\sqrt{p^{\ast }})/\mathbb{Q}}{\cdot }\right)\subset I_{\mathbb{Q}(\sqrt{p^{\ast }})}(p\mathrm{\infty })$,

дакле Лежандров симбол $\left(\frac{p^{\ast }}{\cdot }\right)$ даје групни епиморфизам

$I_{\mathbb{Q}}(p\mathrm{\infty })/P_{\mathbb{Q},1}(p\mathrm{\infty })\to \{\pm 1\}.$

Ово индукује групни епиморфизам

$\left(\frac{p^{\ast }}{\cdot }\right):(\mathbb{Z}/p\mathbb{Z}{)}^{\times }\to \{\pm 1\}.$

Међутим, Лежандров симбол $\left(\frac{\cdot }{p}\right)$ је такође такав, а пошто је $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$ циклична, постоји само један такав хомоморфизам. Следи

$\left(\frac{p^{\ast }}{q}\right)=\left(\frac{q}{p}\right)$.

Литература

• Шаблон:Cite book
• Шаблон:Cite book Birkhäuser
• Komaravolu Chandrasekharan: Шаблон:Cite book Springer-Verlag Berlin / Heidelberg / New York / Tokyo, Grundlehren der mathematischen Wissenschaften 281, .
• Шаблон:Cite book
• David A. Cox: Primes of the Form $x^2+n{y}^2$, Pure and Applied Mathematics: A Wiley Series of Texts, Monographs, and Tracts. Wiley 2013, Second Edition. Шаблон:ISBN.
• Шаблон:Cite book Springer Monographs in Mathematics. Springer Verlag, 2000, .
• Eugen Netto (Hrsg.): Sechs Beweise des Fundamentaltheorems über quadratische Reste von Carl Friedrich Gauß. Verlag Wilhelm Engelmann, Leipzig 1901, дигитализована верзија.
• Jürgen Neukirch: Шаблон:Cite book Springer-Verlag, Berlin/Heidelberg .
• Alexander Schmidt: Шаблон:Cite book
• Шаблон:Cite book. John Wiley & Sons 1983, .
• Шаблон:Cite book. Lecture Notes in Mathematics 2171, Springer Verlag, .

Литература

• Шаблон:Cite book

Спољашње везе

• Списак пронађених доказа квадратног закона реципроцитета