Kvadratisk rest
I matematik , mere præcist i modulær aritmetik , er et naturligt tal q en kvadratisk rest modulo p, hvis den har en kvadratrod i modulær aritmetik af modul p . Med andre ord er q en kvadratisk restmodul p, hvis der findes et heltal x sådan, at:
x2≡q(mods){\ displaystyle {x ^ {2}} \ equiv q {\ pmod {p}}}.
Ellers siger vi, at q er en kvadratisk ikke- restmodul p
Eksempler
For eksempel :
- modulo 4, er de kvadratiske rester de heltal, der er kongruente til 2 2 ≡ 0 2 = 0 eller til (± 1) 2 = 1, hvorfor de kvadratiske ikke-rester er de, der er kongruente til 2 eller 3;
- modulo 2, ethvert heltal er en kvadratisk rest;
- modulo p , er ethvert multiplum af p en kvadratisk rest. Af denne grund udelukker nogle forfattere multiplerne af p fra definitionen og pålægger endda, at p og q er coprime .
Modul ethvert heltal
Modul et helt tal n > 0 , klassen x 2 afhænger kun af x , så de kvadratiske rester er de resterende opnået i den euklidiske division af x 2 ved n ved at variere x i , eller i et hvilket som helst sæt n heltal på hinanden følgende ligesom ( dvs. d. hvis n er lige, og hvis n er ulige).
{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øjre \ rfloor \ højre \}} {-ikke2+1,...,ikke2}{\ displaystyle \ left \ {- {\ frac {n} {2}} + 1, \ prikker, {\ frac {n} {2}} \ højre \}}{-ikke-12,...,ikke-12}{\ displaystyle \ left \ {- {\ frac {n-1} {2}}, \ dots, {\ frac {n-1} {2}} \ right \}}
Vi kan endda begrænse os 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}}
Desuden er 0 og 1 altid kvadratiske rester.
Eksempel:
Nedenstående tabel over modulo 10 kvadratiske rester viser symmetrien godt og viser, at vi kan begrænse os 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} & {\ farve {rød} 0} & {\ farve {grøn} 1} & {\ farve {blå} 4} & {\ farve {cyan} 9} & {\ farve {magenta} 6} & {\ farve {brun} 5 } \ end {array}}}
Lad a og b være to heltal mellem dem. Et heltal x er en kvadratisk restmod ab, hvis (og selvfølgelig kun hvis) er en kvadratisk rest af både mod a og mod b .
x{\ displaystyle x}
Demonstration
Hvis og , lad (af kinesisk restsætning ) være et heltal således, at og . Derefter og derfor (ved Gauss's 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 egenskab gør det muligt at reducere bestemmelsen af de kvadratiske rester modulo ethvert heltal til resterne modulo styrkerne af primtal, der vises i dets nedbrydning .
Modulo et ulige primtal
Lad p være et ulige primtal. For ethvert heltal n er Legendre-symbolet ( n / p ) værd, pr. Definition:
(ikkes)={0 hvis ikke kan deles af s+1 hvis ikke kan ikke deles med s og er en kvadratisk rest modulo s-1 hvis ikke er ikke en modulær 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. \ end {cases}}}I henhold til Eulers kriterium er det kongruent modulo p til n ( p –1) / 2 . The Gauss lemma fremlægger et andet udtryk.
Den kvadratiske gensidighedslov giver os mulighed for at beregne (–1 / p ), (2 / p ) og, hvis q er et andet ulige primtal, ( q / p ) som en funktion af ( p / q ). Det giver for eksempel for et givet heltal n et kriterium for primtalet p med hensyn til modulo 4 n kongruensklasser , der bestemmer, om n er en modulo p kvadratisk rest . Den Aritmetikkens progression gør det muligt at udlede, at hvis n er ikke en perfekt kvadrat , der eksisterer en uendelighed af primtal modulo som n ikke er en kvadratisk rest, og at for enhver endelig mængde , eksisterer der en uendelighed af primtal , således at hvert element af er en firkant .
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 rester er 0 og heltalene i form 4 k (8 m + 1).
For p prime ulige, ethvert heltal ikke er deleligt med p , som er en firkantet mod p er også en firkantet mod p r - ja, gruppe af enheder (ℤ / p r ℤ) × af ℤ / p r ℤ er cyklisk , frembragt af [α (1 + p ) mod p r ] hvor [α mod p ] er en generator af (ℤ / p ℤ) × , eller hvis [(α (1 + p )) s mod p ] = [α s mod p ] er en firkant, så s er jævn - og de kvadratiske rester mod p r er p k n med k ≥ r , eller ( n / p ) = 1 og k end < r .
Beliggenhed
Lad p være et ulige primtal. Det mindste heltal n er ikke en kvadratisk rest modulo p kontrol og selv hvis , .
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}
Mere generelt antager vi, at for alle , for ethvert tilstrækkeligt stort primtal p , er dette heltal n mindre end .
ε>0{\ displaystyle \ varepsilon> 0}sε{\ displaystyle p ^ {\ varepsilon}}
Noter og referencer
(en) Denne artikel er helt eller delvist hentet fra den
engelske Wikipedia- artikel med titlen
" Quadratic residue " ( se listen over forfattere ) .
-
Gauss , § 96 og 105.
-
(i) Kenneth Irland og Michael Rosen , en klassisk introduktion til moderne talteori , Springer , al. " GTM " ( nr . 84);1990( læs online ) , s. 50.
-
(i) Steve Wright, Kvadratisk Rester og ikke-rester: Udvalgte emner Springer al. "Forelæsningsnotater i matematik" ( nr . 2171),2016( arXiv 1408.0235 , læs online ), Sætninger 4.2 og 4.3, og " Mønstre af kvadratiske rester og ikke-restprodukter til uendeligt mange primtal ", J. Number Theory , bind. 123, nr . 1,2007, s. 120-132 ( DOI 10.1016 / j.jnt.2006.06.003 ). For en samtidig generalisering af disse to sætninger, se denne øvelse korrigeret fra lektionen "Introduktion til talteori" på Wikiversity .
-
Pascal Boyer, Lille ledsager af numre og deres applikationer , Paris, Calvage og Mounet,2019, 648 s. ( ISBN 978-2-916352-75-6 ) , Aritmetik af ℤ, kap. I.3.2 (“Kvadratiske rester: applikationer”), s. 47-49.
-
For et bevis uden den aritmetiske progression sætning, se (for n ∈ ℕ) Irland og Rosen 1990 , s. 57-58 (kap. 5, § 2, th. 3) eller (for n ∈ ℤ) denne rettede opgave fra lektionen ”Introduktion til talteori” på Wikiversity .
-
Om relaterede spørgsmål, se " sætning Grunwald-Wang " og (i) " Findes der et ikke-kvadratisk antal qui er den kvadratiske rest af hver præmie? » , Om MathOverflow .
-
Mere præcist er den relative asymptotiske tæthed D (i sættet med primtal) for det uendelige sæt opløsninger ikke-nul og kan udtrykkes simpelt: vi reducerer let (ved at fjerne de overflødige elementer fra S ) til det tilfælde, hvor ingen produkt af elementer af S er en firkant bortset fra det tomme produkt , og vi beviser, at D = 2 - | S | , ved hjælp af den kvantitative version af den aritmetiske progression sætning : se Wright 2016 (th. 4.9) eller (en) R. Balasubramanian (en) , F. Luca og R. Thangadurai, “ On the exact degree of over » , Proc. Bitter. Matematik. 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 (meget enklere) for den øvelse, der er rettet på Wikiversity, der allerede er nævnt.
Se også
Relaterede artikler
eksterne links
- (da) Eric W. Weisstein , " Quadratic Residue " , på MathWorld
- (en) Walter D. Stangl , " Counting Squares in ℤ n " , Math. Mag. , Vol. 69, nr . 4,1996, s. 285-289 ( læs online )
-
CF Gauss , aritmetisk forskning ( læs 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;">