Kvadratisk lov om gensidighed

Den kvadratiske lov om reciprocitet er en række udsagn om løseligheden af ​​en kvadratisk kongruens modulo . Ifølge denne lov, hvis er ulige primtal, og mindst et af dem har formen, så er der to sammenligninger

enten har begge løsninger til eller har begge ikke. Derfor er ordet "gensidighed" brugt i lovens titel. Hvis begge har formen , har løsningen kun én og én af de angivne sammenligninger [1] .

Relaterede definitioner

Hvis sammenligningen for givne heltal har løsninger, så kaldes den kvadratisk rest [2] modulo, og hvis der ikke er nogen løsninger, så kvadratisk non-residue modulo Ved hjælp af denne terminologi kan vi formulere den kvadratiske reciprocitetslov som følger:

Hvis er ulige primtal, og mindst én af dem har formen, så er begge kvadratiske rester modulo hinanden, eller begge er ikke-rester. Hvis begge har formen, så er den kvadratiske rest én og kun ét af disse tal - enten modulo eller modulo

Lad være et heltal, være et ulige primtal. Legendre-symbolet er defineret som følger:

Eksempler på gensidighed for primtal fra 3 til 97

Tabellen nedenfor viser tydeligt, hvilke ulige primtal op til 100 der er rester, og hvilke der er ikke-rester. For eksempel refererer den første linje til modulo 3 og betyder, at tallet 5 er en kvadratisk ikke-rest (H), 7 er en rest (B), 11 er en ikke-rest osv. Tabellen viser tydeligt, at for tal af formen (grønne og blå celler ) er alle koder, der er symmetriske med dem i forhold til matrixens hoveddiagonal, nøjagtig de samme, hvilket er, hvad "gensidighed" betyder. For eksempel har celle (5, 7) den samme kode som celle (7, 5). Hvis cellerne svarer til to tal i formen (gule og røde celler), så er koderne modsatte - for eksempel for (11, 19).

Forklaringer:
q er en rest modulo p    q ≡ 1 (mod 4) eller p ≡ 1 (mod 4) (eller begge)  
H q er en ikke-rest modulo p  
q er en rest modulo p både q ≡ 3 (mod 4) og p ≡ 3 (mod 4)
H q er en ikke-rest modulo p  
q
3 5 7 elleve 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
s 3   H H H H H H H H H H H H
5 H   H H H H H H H H H H H H
7 H H   H H H H H H H H H H H H
elleve H   H H H H H H H H H H
13 H H H   H H H H H H H H H H H H
17 H H H H   H H H H H H H H H H
19 H H   H H H H H H H H H H H
23 H H H H H   H H H H H H H H H
29 H H H H   H H H H H H H H H H
31 H H H H H H   H H H H H H H H
37 H H H H H H H   H H H H H H
41 H H H H H H H   H H H H H H H
43 H H H H H H   H H H H
47 H H H H H H H H H   H H
53 H H H H H H   H H H H H H
59 H H H H H H H   H H H H H H
61 H H H H H H H H H H   H H H H
67 H H H H H H H H H H   H H
71 H H H H H H H H H H H H   H
73 H H H H H H H H H H H   H
79 H H H H H H H H H H H H  
83 H H H H H H H H H H   H H
89 H H H H H H H H H H H H H  
97 H H H H H H H H H H H H H  

Ordlyd med Legendre-symboler

Gauss' kvadratiske reciprocitetslov for Legendre-symboler siger det

hvor p og q er forskellige ulige primtal.

Følgende tilføjelser er også gyldige :

og

Konsekvenser

Desuden er dette tegn også et kriterium, det vil sige en sammenligning modulo primtal kan afgøres, hvis og kun hvis Ved at bruge Legendre-symbolet kan den sidste påstand udtrykkes som følger: løses af en algoritme ved hjælp af multiplikativiteten af ​​Legendre-symbolet og den kvadratiske lov om gensidighed.

Eksempler på brug

Derfor sammenligningen har en løsning.

Historie

Formuleringen af ​​den kvadratiske reciprocitetslov var allerede kendt af Euler i 1783 [3] . Legendre formulerede loven uafhængigt af Euler og beviste den i nogle særlige tilfælde i 1785. Et fuldstændigt bevis blev udgivet af Gauss i Arithmetical Investigations (1801); efterfølgende gav Gauss flere flere af sine beviser, baseret på helt andre ideer.

Et af de enkleste bevis blev foreslået af Zolotarev i 1872. [4] [5] [6]

Efterfølgende blev der opnået forskellige generaliseringer af den kvadratiske reciprocitetslov [7] .

Variationer og generaliseringer

Se også

Noter

  1. Carl Friedrich Gauss. Proceedings on talteori / Generel udgave af akademiker I. M. Vinogradov , kommentarer fra tilsvarende medlem. USSR's Videnskabsakademi B.N. Delaunay . - M. : Publishing House of the Academy of Sciences of the USSR, 1959. - S. 126. - 297 s. - (videnskabens klassikere).
  2. Quadratic Residue // Mathematical Encyclopedia (i 5 bind). - M .: Soviet Encyclopedia , 1979. - T. 2. - S. 785-786.
  3. Euler, Opuscula analytica, Petersborg, 1783.
  4. Zolotareff G. Nouvelle demonstration de la loi de de réciprocité de Legendre  (fransk)  // Nouvelles Annales de Mathématiques, 2e serie: magazine. - 1872. - Bd. 11 . - S. 354-362 .  (utilgængeligt link)
  5. Prasolov V.V. Bevis for den kvadratiske lov om gensidighed ifølge Zolotarev  // Matematisk uddannelse . - 2000. - T. 4 . - S. 140-144 .
  6. Gorin E. A. Permutationer og den kvadratiske lov om gensidighed ifølge Zolotarev-Frobenius-Rousseau  // Chebyshev-samlingen. - 2013. - T. 14 , no. 4 . - S. 80-94 .
  7. Irland K., Rosen M.  En klassisk introduktion til moderne talteori.

Litteratur

Links