Toissijainen jäännös
On matematiikka , tarkemmin sanoen modulaarinen aritmetiikka , joka on luonnollinen luku q on neliöllinen jäännös modulo p , jos se on neliöjuuri on modulaarinen aritmetiikka moduli on s . Toisin sanoen q on asteen jäännös modulo p, jos on olemassa kokonaisluku x , joka:
x2≡q(mods){\ displaystyle {x ^ {2}} \ equiv q {\ pmod {p}}}![{\ displaystyle {x ^ {2}} \ equiv q {\ pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/148251f0996fa22d562d122226cb74367e332b3d)
.
Muuten, sanomme, että q on neliöllinen ei tähteen modulo p
Esimerkkejä
Esimerkiksi :
- modulo 4, neliölliset tähteet ovat kokonaislukuja, jotka ovat yhteneväisiä 2 2 × 0 2 = 0: n tai (± 1) 2 = 1: n kanssa, joten neliölliset ei-tähteet ovat yhtäpitäviä 2: n tai 3: n kanssa;
- moduuli 2, mikä tahansa kokonaisluku on neliöllinen tähde;
- modulo p , mikä tahansa monikerta p on neliönjäännös. Tästä syystä jotkut kirjoittajat sulkevat p: n kerrannaiset pois määritelmästä ja jopa määräävät, että p ja q ovat yhteistä .
Modulo mikä tahansa kokonaisluku
Modulo kokonaisluku n > 0 , luokka x 2 riippuu ainoastaan että x , joten neliönjäännös ovat jäännöksistä saadaan jakoyhtälö on x 2 mukaan n vaihtelemalla x on , tai mikä tahansa joukko n kokonaislukuja peräkkäisen, kuten ( eli d. jos n on parillinen ja jos n on pariton).
{0,1,...,ei-1}{\ displaystyle \ vasen \ {0,1, \ pisteet, n-1 \ oikea \}}
{⌊-ei2⌋+1,⌊-ei2⌋+2,...,⌊ei2⌋}{\ displaystyle \ left \ {\ left \ lfloor {\ frac {-n} {2}} \ right \ rfloor +1, \ left \ lfloor {\ frac {-n} {2}} \ right \ rfloor +2 , \ pisteet, \ vasen \ lfloor {\ frac {n} {2}} \ right \ rfloor \ right \}}
{-ei2+1,...,ei2}{\ displaystyle \ left \ {- {\ frac {n} {2}} + 1, \ pisteet, {\ frac {n} {2}} \ oikea \}}
{-ei-12,...,ei-12}{\ displaystyle \ left \ {- {\ frac {n-1} {2}}, \ pisteet, {\ frac {n-1} {2}} \ oikea \}}![{\ displaystyle \ left \ {- {\ frac {n-1} {2}}, \ pisteet, {\ frac {n-1} {2}} \ oikea \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca44f6882de360c30838abac5e72d011303c0731)
Voimme jopa rajoittua siihen , siitä lähtien .
x∈{0,1,...,⌊ei2⌋}{\ displaystyle x \ in \ left \ {0,1, ..., \ left \ lfloor {\ frac {n} {2}} \ right \ rfloor \ right \}}
(-x)2=x2{\ displaystyle \ vasen (-x \ oikea) ^ {2} = x ^ {2}}![{\ displaystyle \ vasen (-x \ oikea) ^ {2} = x ^ {2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d10284cc18c947e3c4831752edd47aa826ee60c4)
Lisäksi 0 ja 1 ovat aina neliöllisiä tähteitä.
Esimerkki:
Alla olevassa taulukossa modulo 10: n toisen asteen jäännökset osoittavat symmetrian hyvin ja osoittavat, että voimme rajoittua .
x∈{0,1,...,5}{\ displaystyle x \ sisään \ {0,1, ..., 5 \}}![{\ displaystyle x \ sisään \ {0,1, ..., 5 \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe9e3bdb20bf49d21307ccd17d93cd938c34957e)
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} & {\ väri {punainen} 0} ja {\ väri {vihreä} 1} ja {\ väri {sininen} 4} ja {\ väri {syaani} 9} ja {\ väri {magenta} 6} ja {\ väri {ruskea} 5 } \ end {array}}}
Olkoon a ja b kaksi kokonaislukua alkupäässä. Kokonaisluku x on neliönjäännös mod ab jos (ja tietenkin vain jos) on neliöllinen jäännös sekä mod ja mod b .
x{\ displaystyle x}![x](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4)
Esittely
Jos ja , olkoon ( kiinalaisen jäännöslauseen mukaan ) sellainen kokonaisluku , että ja . Sitten ja siksi ( Gaussin lemman mukaan ) .
x≡u2modklo{\ displaystyle x \ equiv u ^ {2} {\ bmod {a}}}
x≡v2modb{\ displaystyle x \ equiv v ^ {2} {\ bmod {b}}}
w{\ displaystyle w}
w≡umodklo{\ displaystyle w \ equiv u {\ bmod {a}}}
w≡vmodb{\ displaystyle w \ equiv v {\ bmod {b}}}
x≡w2modklo{\ displaystyle x \ equiv w ^ {2} {\ bmod {a}}}
x≡w2modb{\ displaystyle x \ equiv w ^ {2} {\ bmod {b}}}
x≡w2modklob{\ displaystyle x \ equiv w ^ {2} {\ bmod {ab}}}![{\ displaystyle x \ equiv w ^ {2} {\ bmod {ab}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/00bb4b72f22aa7a68c0769ca16afa7e2eb124773)
Tämä ominaisuus tekee mahdolliseksi pienentää neliöllisten tähteiden määritystä moduloida mikä tahansa kokonaisluku jäännösten määräksi modulo alkulukujen voimia, jotka esiintyvät sen hajoamisessa .
Olkoon p pariton alkuluku. Tahansa kokonaisluku n , The Legendren symboli ( n / p ) on arvoltaan, määritelmän:
(eis)={0 jos ei on jaettavissa s+1 jos ei ei ole jaettavissa s ja on neliöllinen jäännösmoduuli s-1 jos ei ei ole modulo-neliöllinen jäännös s.{\ displaystyle \ left ({\ frac {n} {p}} \ right) = {\ begin {cases} \; \; \, 0 & {\ text {si}} n {\ text {on jaollinen} } p \\ + 1 ja {\ text {si}} n {\ text {ei ole jaettavissa luvulla}} p {\ text {ja se on neliöllinen jäännösmoduuli}} p \\ - 1 & {\ text {si} } n {\ text {ei ole neliöllinen jäännösmoduuli}} p. \ end {cases}}}![{\ displaystyle \ left ({\ frac {n} {p}} \ right) = {\ begin {cases} \; \; \, 0 & {\ text {si}} n {\ text {on jaollinen} } p \\ + 1 ja {\ text {si}} n {\ text {ei ole jaettavissa luvulla}} p {\ text {ja se on neliöllinen jäännösmoduuli}} p \\ - 1 & {\ text {si} } n {\ text {ei ole neliöllinen jäännösmoduuli}} p. \ end {cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/17bb6f4c8baf68a40ad3bd201ed3d92977f7b3bd)
Mukaan Eulerin kriteerin , se on yhtenevä modulo p ja n ( p -1) / 2 . Gauss Lemma toimittaa toisen lausekkeen.
Neliöllinen laki vastavuoroisuuden avulla voimme laskea (-1 / p ), (2 / p ), ja jos q on toinen pariton alkuluku, ( q / p ) funktiona ( p / q ). Se tarjoaa esimerkiksi tietylle kokonaisluvulle n kriteerin alkuluvulle p modulo 4 n- kongruenssiluokkien perusteella , mikä määrittää, onko n modulo p -nopeusjäännös . Lause aritmeettinen etenemisen tekee mahdolliseksi päätellä, että jos n ei ole täydellinen neliö , on olemassa ääretön alkulukujen modulo joka n ei ole neliönjäännös, ja että mikä tahansa äärellinen joukko , on olemassa ääretön alkuluvut siten, että jokainen elementti on neliö .
S⊂Z{\ displaystyle S \ osajoukko \ mathbb {Z}}
s{\ displaystyle p}
S{\ displaystyle S}
mods{\ displaystyle {\ bmod {p}}}![{\ displaystyle {\ bmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f1460330b9d39cce63f1625732fd347e4a92fda9)
Modulo 2 r, kun r ≥ 3, neliölliset jäännökset ovat 0 ja muodon 4 k kokonaisluvut (8 m + 1).
Ja p prime pariton, mikä tahansa kokonaisluku ole jaollinen p , joka on neliön mod p on myös neliön mod p r - todellakin, yksikköjen ryhmän (ℤ / p r ℤ) x on ℤ / p r ℤ on syklinen , syntyy [α (1 + p ) mod p r ], jossa [α mod p ] on (ℤ / p ℤ) ×: n generaattori , tai jos [(α (1 + p )) s mod p ] = [α s mod p ] on neliö, sitten s on parillinen - ja neliölliset jäännökset mod p r ovat p k n, kun k ≥ r tai ( n / p ) = 1 ja k jopa < r .
Sijainti
Olkoon p pariton alkuluku. Pienin kokonaisluku n ei ole neliönjäännös modulo p tarkistaa ja vaikka , .
ei<1+s{\ displaystyle n <1 + {\ sqrt {p}}}
s≢1(mod8){\ displaystyle p \ not \ equiv 1 {\ pmod {8}}}
ei<s25+12s15+33{\ displaystyle n <p ^ {\ frac {2} {5}} + 12p ^ {\ frac {1} {5}} + 33}![{\ displaystyle n <p ^ {\ frac {2} {5}} + 12p ^ {\ frac {1} {5}} + 33}](https://wikimedia.org/api/rest_v1/media/math/render/svg/463a579243224c58ab37d57e043db0e03dbbb3ca)
Oletetaan yleisesti, että kaikille riittävän suurille alkuluvuille p tämä kokonaisluku n on pienempi kuin .
e>0{\ displaystyle \ varepsilon> 0}
se{\ displaystyle p ^ {\ varepsilon}}![{\ displaystyle p ^ {\ varepsilon}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10ab6c7633b2292db8a171e02b1075054448b91c)
Huomautuksia ja viitteitä
(fr) Tämä artikkeli on osittain tai kokonaan peräisin
englanninkielisestä Wikipedia- artikkelista
" Quadratic residual " ( katso luettelo kirjoittajista ) .
-
Gauss , § 96 ja 105.
-
(in) Kenneth Irlannissa ja Michael Rosen , klassinen Johdatus Modern Lukuteoria , Springer , ai. " GTM " ( n o 84);1990( lue verkossa ) , s. 50.
-
(in) Steve Wright, neliönjäännös ja Non-jäännökset: valituista aiheista Springer ai. "Lecture Notes in Mathematics" ( n o 2171),2016( arXiv 1408.0235 , lue verkossa ), Lauseet 4.2 ja 4.3 sekä ” Toissijaisten jäännösten ja jäännösten mallit äärettömän monelle alkulle ”, J. Number Theory , voi. 123, n o 1,2007, s. 120-132 ( DOI 10.1016 / j.jnt.2006.06.003 ). Samanaikaista yleistys näiden kahden lauseet, katso tämä harjoitus korjattu oppiaiheesta "Johdatus lukuteoriaan" päälle Wikikirjasto .
-
Pascal Boyer, pieni kumppani numeroista ja niiden sovelluksista , Pariisi, Calvage ja Mounet,2019, 648 Sivumäärä ( ISBN 978-2-916352-75-6 ) , ℤ: n aritmeetti, luku . I.3.2 (”Toissijaiset jäännökset: sovellukset”), s. 47-49.
-
Katso todiste ilman aritmeettisen etenemislauseen ( n ∈ ℕ: lle) Irlanti ja Rosen 1990 , s. 57–58 (luku 5, § 2, th. 3) tai ( n: lle ℤ ℤ) tämä korjattu tehtävä opetuksesta "Johdatus lukuteoriaan" Wikikorkeakoulusta .
-
aiheeseen liittyvistä aiheista lause " Grunwald-Wang " ja (in) " Onko olemassa ei-neliönumeroa, qui on jokaisen palkkion neliöllinen jäännös? » , MathOverflow .
-
Tarkemmin sanottuna äärettömän ratkaisusarjan suhteellinen asymptoottinen tiheys D (alkulukujoukossa) ei ole nolla ja voidaan ilmaista yksinkertaisesti: pienennämme helposti (poistamalla S: stä redundantit elementit) tapaukseen, jossa ei ole S : n alkioiden tulo on neliö erillään tyhjästä tuotteesta , ja todistamme, että silloin D = 2 - | S | käyttäen aritmeettisen etenemislausekkeen kvantitatiivista versiota : katso Wright 2016 (th. 4.9) tai (en) R. Balasubramanian (en) , F. Luca ja R. Thangadurai, “ On the specific rate of over ” , Proc. Katkera. Matematiikka. Soc. , voi. 138,s{\ displaystyle p}
Q(klo1,klo2,...,kloℓ){\ 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 ), tai todiste (paljon yksinkertaisempi) harjoituksesta, joka on jo korjattu Wikikirjassa .
Katso myös
Aiheeseen liittyvät artikkelit
Ulkoiset linkit
- (en) Eric W. Weisstein , ” Toissijainen jäännös ” , MathWorldissa
- (en) Walter D. Stangl , ” Neliöiden laskeminen ℤ n: ssä ” , Math. Mag. , voi. 69, n o 4,1996, s. 285-289 ( lue verkossa )
-
CF Gauss , aritmeettinen tutkimus ( lue verkossa ), 101 ja 102 §
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">