Kvadratiske rester
I matematikk , nærmere bestemt i modulær aritmetikk , er et naturlig tall q en kvadratisk rest modulo p hvis den har en kvadratrot i modulær aritmetikk av modul p . Med andre ord er q en kvadratisk restmodul p hvis det eksisterer et helt tall x slik at:
x2≡q(mods){\ displaystyle {x ^ {2}} \ equiv q {\ pmod {p}}}.
Ellers sier vi at q er en kvadratisk ikke- restmodul p
Eksempler
For eksempel :
- modulo 4, er de kvadratiske restene heltallene som er kongruente til 2 2 ≡ 0 2 = 0 eller til (± 1) 2 = 1, derfor er de kvadratiske ikke-restene de som er kongruente til 2 eller 3;
- modulo 2, ethvert heltall er en kvadratisk rest;
- modulo p , er hvilket som helst multiplum av p en kvadratisk rest. Av denne grunn ekskluderer noen forfattere multipler av p fra definisjonen og til og med pålegger at p og q er koprime .
Moduler hvilket som helst heltall
Modulo et heltall n > 0 , klassen x 2 avhenger bare av x , så de kvadratiske restene er resten som oppnås i den euklidiske divisjonen av x 2 ved n ved å variere x i , eller i et sett med n heltall påfølgende, som ( dvs. d. hvis n er jevn og hvis n er merkelig).
{0,1,...,ikke-1}{\ displaystyle \ left \ {0,1, \ dots, n-1 \ right \}}{⌊-ikke2⌋+1,⌊-ikke2⌋+2,...,⌊ikke2⌋}{\ displaystyle \ left \ {\ left \ lfloor {\ frac {-n} {2}} \ right \ rfloor +1, \ left \ lfloor {\ frac {-n} {2}} \ right \ rfloor +2 , \ prikker, \ venstre \ lfloor {\ frac {n} {2}} \ høyre \ rfloor \ høyre \}} {-ikke2+1,...,ikke2}{\ displaystyle \ left \ {- {\ frac {n} {2}} + 1, \ prikker, {\ frac {n} {2}} \ høyre \}}{-ikke-12,...,ikke-12}{\ displaystyle \ left \ {- {\ frac {n-1} {2}}, \ prikker, {\ frac {n-1} {2}} \ høyre \}}
Vi kan til og med begrense oss til , siden .
x∈{0,1,...,⌊ikke2⌋}{\ displaystyle x \ in \ left \ {0,1, ..., \ left \ lfloor {\ frac {n} {2}} \ right \ rfloor \ right \}}(-x)2=x2{\ displaystyle \ left (-x \ right) ^ {2} = x ^ {2}}
Videre er 0 og 1 alltid kvadratiske rester.
Eksempel:
Tabellen nedenfor over modulo 10 kvadratiske rester viser symmetrien godt og viser at vi kan begrense oss til .
x∈{0,1,...,5}{\ displaystyle x \ in \ {0,1, ..., 5 \}}
x-4-3-2-1012345x26941014965{\ displaystyle {\ begin {array} {| c | c | c | c || c | c | c |} x & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 \\\ hline x ^ {2} & {\ color {magenta} 6} & {\ color {cyan} 9} & {\ color {blue} 4} & {\ color {green} 1} & {\ farge {rød} 0} og {\ farge {grønn} 1} & {\ farge {blå} 4} og {\ farge {cyan} 9} & {\ farge {magenta} 6} og {\ farge {brun} 5 } \ end {array}}}
La a og b være to heltall mellom dem. Et helt tall x er en kvadratisk restmod ab hvis (og selvfølgelig bare hvis) er en kvadratisk rest av både mod a og mod b .
x{\ displaystyle x}
Demonstrasjon
Hvis og , la (av Chinese Remainder Theorem ) være et helt tall slik at og . Da, og derfor (av Gauss lemma ) .
x≡u2modpå{\ displaystyle x \ equiv u ^ {2} {\ bmod {a}}}x≡v2modb{\ displaystyle x \ equiv v ^ {2} {\ bmod {b}}}w{\ displaystyle w}w≡umodpå{\ displaystyle w \ equiv u {\ bmod {a}}}w≡vmodb{\ displaystyle w \ equiv v {\ bmod {b}}}x≡w2modpå{\ displaystyle x \ equiv w ^ {2} {\ bmod {a}}}x≡w2modb{\ displaystyle x \ equiv w ^ {2} {\ bmod {b}}}x≡w2modpåb{\ displaystyle x \ equiv w ^ {2} {\ bmod {ab}}}
Denne egenskapen gjør det mulig å redusere bestemmelsen av kvadratiske rester modulo hvilket som helst heltall til rester modulo kraftene til primtall som vises i nedbrytningen .
La p være et oddetall. For et hvilket som helst heltall n , den Legendre symbol ( n / p ) er verdt, ved definisjon:
(ikkes)={0 hvis ikke er delelig med s+1 hvis ikke er ikke delelig med s og er en kvadratisk rest modulo s-1 hvis ikke er ikke en modulo kvadratisk rest s.{\ displaystyle \ left ({\ frac {n} {p}} \ right) = {\ begin {cases} \; \; \, 0 & {\ text {si}} n {\ text {kan deles med} } p \\ + 1 & {\ text {si}} n {\ text {kan ikke deles med}} p {\ text {og er en kvadratisk restmodul}} p \\ - 1 & {\ text {si} } n {\ text {er ikke en kvadratisk restmodul}} s. \ slutt {cases}}}I følge Eulers kriterium er det kongruent modulo p til n ( p –1) / 2 . Den Gauss lemma forsyner et annet uttrykk.
Den kvadratiske gjensidighetsloven lar oss beregne (–1 / p ), (2 / p ) og, hvis q er et annet oddetall, ( q / p ) som en funksjon av ( p / q ). Det gir for eksempel for et gitt heltall n et kriterium for primtallet p i form av modulo 4 n kongruensklasser , som bestemmer om n er en modulo p kvadratisk rest . Den teorem av aritmetisk progresjon gjør det mulig å utlede at hvis n er ikke en perfekt firkantet , eksisterer en uendelighet av primtall modulo som n ikke er en kvadratisk rest, og at for enhver endelig sett eksisterer det en uendelighet av primtall slik det hvert element av er et kvadrat .
S⊂Z{\ displaystyle S \ subset \ mathbb {Z}}s{\ displaystyle p}S{\ displaystyle S}mods{\ displaystyle {\ bmod {p}}}
Modulo 2 r med r ≥ 3, de kvadratiske restene er 0 og heltallene i skjemaet 4 k (8 m + 1).
For p prime oddetall, en hvilken som helst heltall som ikke er delelig med p som er en firkantet mod p er også et firkantet mod p r - ja, den gruppen av enheter (ℤ / p r ℤ) x av ℤ / p r ℤ er syklisk , generert av [α (1 + p ) mod p r ] hvor [α mod p ] er en generator av (ℤ / p ℤ) × , eller hvis [(α (1 + p )) s mod p ] = [α s mod p ] er en firkant så er s jevn - og de kvadratiske restene mod p r er p k n med k ≥ r , eller ( n / p ) = 1 og k til og med < r .
plassering
La p være et oddetall. Den minste heltall n er ikke en kvadratisk rest modulo p sjekker og selv om , .
ikke<1+s{\ displaystyle n <1 + {\ sqrt {p}}}s≢1(mod8){\ displaystyle p \ not \ equiv 1 {\ pmod {8}}}ikke<s25+12s15+33{\ displaystyle n <p ^ {\ frac {2} {5}} + 12p ^ {\ frac {1} {5}} + 33}
Mer generelt antar vi at for alt , for et tilstrekkelig stort primtall p , er dette heltallet n mindre enn .
ε>0{\ displaystyle \ varepsilon> 0}sε{\ displaystyle p ^ {\ varepsilon}}
Merknader og referanser
(no) Denne artikkelen er helt eller delvis hentet fra den
engelske Wikipedia- artikkelen med tittelen
" Quadratic residue " ( se listen over forfattere ) .
-
Gauss , § 96 og 105.
-
(in) Kenneth Ireland og Michael Rosen , En klassisk introduksjon til moderne tallteori , Springer , al. " GTM " ( N o 84);1990( les online ) , s. 50.
-
(in) Steve Wright, kvadratiske rester og ikke-rester: utvalgte emner Springer al. "Lecture Notes-i Mathematics" ( n o 2171),2016( arXiv 1408.0235 , les online ), Teoremer 4.2 og 4.3, og “ Mønstre av kvadratiske rester og ikke-rester for uendelig mange primtall ”, J. Number Theory , vol. 123, n o 1,2007, s. 120-132 ( DOI 10.1016 / j.jnt.2006.06.003 ). For en samtidig generalisering av disse to setningene, se denne øvelsen korrigert fra leksjonen "Introduksjon til tallteori" på Wikiversity .
-
Pascal Boyer, liten følgesvenn av tall og deres applikasjoner , Paris, Calvage og Mounet,2019, 648 s. ( ISBN 978-2-916352-75-6 ) , Aritmetikk av ℤ, kap. I.3.2 (“Kvadratiske rester: applikasjoner”), s. 47-49.
-
For et bevis uten den aritmetiske progresjonssatsen, se (for n ∈ ℕ) Irland og Rosen 1990 , s. 57-58 (kap. 5, § 2, th. 3) eller (for n ∈ ℤ) denne korrigerte oppgaven fra leksjonen “Introduksjon til tallteori” på Wikiversity .
-
Om relaterte spørsmål, se " teorem Grunwald-Wang " og (i) " Finnes det et ikke-kvadratisk tall qui er kvadratresten av hver premie? » , On MathOverflow .
-
Mer presist, den relative asymptotiske tettheten D (i settet med primtall) for det uendelige settet med løsninger er ikke null og kan uttrykkes enkelt: vi reduserer lett (ved å fjerne de overflødige elementene fra S ) til tilfellet der ingen produktet av elementene i S er et kvadrat bortsett fra det tomme produktet , og vi viser at da er D = 2 - | S | , ved hjelp av den kvantitative versjonen av den aritmetiske progresjonssatsen : se Wright 2016 (th. 4.9) eller (en) R. Balasubramanian (en) , F. Luca og R. Thangadurai, “ On the exact degree of over » , Proc. Bitter. Matte. Soc. , vol. 138,s{\ displaystyle p} Q(på1,på2,...,påℓ){\ displaystyle \ mathbb {Q} ({\ sqrt {a_ {1}}}, {\ sqrt {a_ {2}}}, \ ldots, {\ sqrt {a _ {\ ell}}})}Q{\ displaystyle \ mathbb {Q}}2010, s. 2283-2288 ( DOI 10.1090 / S0002-9939-10-10331-1 ), eller beviset (mye enklere) av øvelsen korrigert på Wikiversity allerede nevnt.
Se også
Relaterte artikler
Eksterne linker
- (no) Eric W. Weisstein , “ Quadratic Residue ” , på MathWorld
- (no) Walter D. Stangl , “ Counting Squares in ℤ n ” , Math. Mag. , vol. 69, n o 4,1996, s. 285-289 ( les online )
-
CF Gauss , aritmetisk forskning ( les online ), § 101 og 102
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">