Kuadratik kalıntı
Gelen matematik , daha kesin olarak modüler aritmetik bir doğal sayı q a, kuadratik kalıntı modülo p bir varsa kare kökü olarak modüler aritmetik katsayısı p . Başka bir deyişle, q , aşağıdaki gibi bir x tamsayısı varsa, ikinci dereceden bir kalıntı modulo p'dir :
x2≡q(modp){\ 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)
.
Aksi takdirde, q'nun kuadratik bir kalıntı olmayan modulo p olduğunu söyleriz.
Örnekler
Örneğin :
- modulo 4, ikinci dereceden kalıntılar, 2 2 ≡ 0 2 = 0 veya (± 1) 2 = 1 ile uyumlu tam sayılardır, bu nedenle ikinci dereceden kalıntı olmayanlar, 2 veya 3 ile uyumlu olanlardır;
- modulo 2, herhangi bir tam sayı ikinci dereceden bir kalıntıdır;
- modülo p , herhangi bir katsayı p ikinci dereceden bir kalıntısıdır. Bu nedenle, bazı yazarlar p'nin katlarını tanımın dışında tutuyor ve hatta p ve q'nun eş asal olmasını dayatıyor .
Herhangi bir tamsayı modulo
Modülo bir tamsayıdır , n > 0 , sınıf x 2 , yalnızca bu bağlıdır x , ikinci dereceden kalıntıları Öklid bölümünde elde kalanlar yani x 2 ile n değiştirilmesiyle x de , ya herhangi bir set içinde n ardışık tamsayılar, gibi ( yani, d. , eğer , n , hatta ve eğer n, tek bir).
{0,1,...,değil-1}{\ displaystyle \ sol \ {0,1, \ noktalar, n-1 \ sağ \}}
{⌊-değil2⌋+1,⌊-değil2⌋+2,...,⌊değil2⌋}{\ displaystyle \ sol \ {\ sol \ lfloor {\ frac {-n} {2}} \ sağ \ rfloor +1, \ sol \ lfloor {\ frac {-n} {2}} \ sağ \ rfloor +2 , \ noktalar, \ sol \ lfloor {\ frac {n} {2}} \ sağ \ rfloor \ sağ \}}
{-değil2+1,...,değil2}{\ displaystyle \ sol \ {- {\ frac {n} {2}} + 1, \ noktalar, {\ frac {n} {2}} \ sağ \}}
{-değil-12,...,değil-12}{\ displaystyle \ sol \ {- {\ frac {n-1} {2}}, \ noktalar, {\ frac {n-1} {2}} \ sağ \}}![{\ displaystyle \ sol \ {- {\ frac {n-1} {2}}, \ noktalar, {\ frac {n-1} {2}} \ sağ \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca44f6882de360c30838abac5e72d011303c0731)
O zamandan beri kendimizi bununla sınırlayabiliriz .
x∈{0,1,...,⌊değil2⌋}{\ displaystyle x \ in \ sol \ {0,1, ..., \ sol \ lfloor {\ frac {n} {2}} \ sağ \ rfloor \ sağ \}}
(-x)2=x2{\ displaystyle \ sol (-x \ sağ) ^ {2} = x ^ {2}}![{\ displaystyle \ sol (-x \ sağ) ^ {2} = x ^ {2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d10284cc18c947e3c4831752edd47aa826ee60c4)
Ayrıca, 0 ve 1 her zaman ikinci dereceden kalıntılardır.
Misal:
Modulo 10 kuadratik kalıntıların aşağıdaki tablosu simetriyi iyi gösterir ve kendimizi sınırlayabileceğimizi gösterir .
x∈{0,1,...,5}{\ displaystyle x \ in \ {0,1, ..., 5 \}}![{\ displaystyle x \ in \ {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 {macenta} 6} & {\ color {cyan} 9} & {\ color {mavi} 4} & {\ color {yeşil} 1} & {\ renk {kırmızı} 0} & {\ renk {yeşil} 1} & {\ renk {mavi} 4} & {\ renk {camgöbeği} 9} & {\ renk {macenta} 6} ve {\ renk {kahverengi} 5 } \ end {dizi}}}
Let bir ve olmak b aralarında iki tamsayılar asal. Bir tam sayı x isimli ikinci dereceden bir tortu mod ab (ve tabii ki sadece bir) her ikisinin bir kuadratik tortusudur mod a ve mod b .
x{\ displaystyle x}![x](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4)
Gösteri
If ve , ( Çin Kalan Teoremine göre ) ve gibi bir tamsayı olsun . Sonra ve bu nedenle ( Gauss'un lemması ile ) .
x≡sen2mod-de{\ displaystyle x \ eşdeğeri u ^ {2} {\ bmod {a}}}
x≡v2modb{\ displaystyle x \ eşdeğeri v ^ {2} {\ bmod {b}}}
w{\ displaystyle w}
w≡senmod-de{\ displaystyle w \ equiv u {\ bmod {a}}}
w≡vmodb{\ displaystyle w \ equiv v {\ bmod {b}}}
x≡w2mod-de{\ displaystyle x \ eşdeğeri w ^ {2} {\ bmod {a}}}
x≡w2modb{\ displaystyle x \ eşdeğeri w ^ {2} {\ bmod {b}}}
x≡w2mod-deb{\ displaystyle x \ eşdeğeri w ^ {2} {\ bmod {ab}}}![{\ displaystyle x \ eşdeğeri w ^ {2} {\ bmod {ab}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/00bb4b72f22aa7a68c0769ca16afa7e2eb124773)
Bu özellik, ikinci dereceden kalıntıların belirlenmesini, herhangi bir tamsayıyı , ayrıştırmada görünen asal sayıların güçlerini modulo olan kalıntılarınkine düşürmeyi mümkün kılar .
Let s olmak bir tek asal sayı. Herhangi bir n tamsayısı için Legendre sembolü ( n / p ) tanımı gereği değerdir:
(değilp)={0 Eğer değil ile bölünebilir p+1 Eğer değil ile bölünemez p ve ikinci dereceden bir kalıntı modulodur p-1 Eğer değil modülo kuadratik bir kalıntı değildir p.{\ displaystyle \ left ({\ frac {n} {p}} \ right) = {\ begin {case} \; \; \, 0 & {\ text {si}} n {\ text {, ile bölünebilir} } p \\ + 1 & {\ text {si}} n {\ text {,}} p {\ text {ile bölünemez ve ikinci dereceden bir artık modulo'dur}} p \\ - 1 & {\ text {si} } n {\ text {ikinci dereceden bir kalıntı modülü değildir}} p. \ end {durumlar}}}![{\ displaystyle \ left ({\ frac {n} {p}} \ right) = {\ begin {case} \; \; \, 0 & {\ text {si}} n {\ text {, ile bölünebilir} } p \\ + 1 & {\ text {si}} n {\ text {,}} p {\ text {ile bölünemez ve ikinci dereceden bir artık modulo'dur}} p \\ - 1 & {\ text {si} } n {\ text {ikinci dereceden bir kalıntı modülü değildir}} p. \ end {durumlar}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/17bb6f4c8baf68a40ad3bd201ed3d92977f7b3bd)
Göre Euler kritere , bu uyumlu modülo olan p için n ( s -1) / 2 . Gauss lemması bir ifade vermektedir.
İkinci dereceden karşılıklılık yasası, (-1 / p ), (2 / p ) ve q başka bir tek asal sayı ise ( q / p ) 'yi ( p / q )' nun bir fonksiyonu olarak hesaplamamıza izin verir . Örneğin, belirli bir n tamsayısı için , n'nin modulo p ikinci dereceden bir kalıntı olup olmadığını belirleyen, modulo 4 n uyum sınıfları açısından asal sayı p üzerinde bir kriter sağlar . Aritmetik ilerleme teoremi eğer anlamak mümkün kılan n bir değil tam kare orada asal bir sonsuzluk modulo bulunduğu, n bir kuadratik kalan değildir ve herhangi bir sonlu seti için bu , asal sayıların bir sonsuzluk vardır öyle ki her eleman bir karedir .
S⊂Z{\ displaystyle S \ alt küme \ mathbb {Z}}
p{\ displaystyle p}
S{\ displaystyle S}
modp{\ displaystyle {\ bmod {p}}}![{\ displaystyle {\ bmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f1460330b9d39cce63f1625732fd347e4a92fda9)
R ≥ 3 ile Modulo 2 r , ikinci dereceden artıklar 0 ve 4 k (8 m + 1) formunun tam sayılarıdır .
İçin p asal tek, bölünemeyen herhangi bir tam sayı , p kare mod p , aynı zamanda, bir kare mod p r - aslında, birim grubu (ℤ / p r ℤ) x ℤ / ve p r ℤ olan siklik tarafından oluşturulan [α (1 + p ) mod p r ] burada [α mod p ] bir (ℤ / p ℤ) × oluşturucusudur veya [(α (1 + p )) s mod p ] = [α s mod p ] kare daha sonra s ve karesel artıklar - mod da bir p r olan p k , n ile k ≥ r , veya ( n / p ) = 1 ve k hatta < r .
yer
Let s olmak bir tek asal sayı. Küçük tam sayı n, ikinci dereceden bir tortu, modülo değildir s kontrol ve bile , .
değil<1+p{\ displaystyle n <1 + {\ sqrt {p}}}
p≢1(mod8){\ displaystyle p \ not \ equiv 1 {\ pmod {8}}}
değil<p25+12p15+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)
Daha genel olarak, varsayım herkes için o herhangi, yeterince büyük asal sayı p , bu tamsayı n az olduğunu .
ε>0{\ displaystyle \ varepsilon> 0}
pε{\ displaystyle p ^ {\ varepsilon}}![{\ displaystyle p ^ {\ varepsilon}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10ab6c7633b2292db8a171e02b1075054448b91c)
Notlar ve referanslar
(fr) Bu makale kısmen veya tamamen alınır
İngilizce Vikipedi başlıklı makalesinde
" Kuadratik kalıntı " ( yazarların listesini görmek ) .
-
Gauss , § 96 ve 105.
-
(in) Kenneth İrlanda ve Michael Rosen , Modern Sayılar Teorisine Bir Klasik Giriş , Springer , ark. " GTM " ( n o 84);1990( çevrimiçi okuyun ) , s. 50.
-
(in) Steve Wright, Kuadratik Kalıntılar ve Kalıntı Olmayanlar: Seçilmiş Konular Springer al. "Matematik Ders Notları" ( n o 2171),2016( arXiv 1408.0235 , çevrimiçi okuyun ), Teorem 4.2 ve 4.3 ve " Sonsuz sayıda asal için ikinci dereceden kalıntıların ve kalıntı olmayanların desenleri ", J. Number Theory , cilt. 123, n o 1,2007, s. 120-132 ( DOI 10.1016 / j.jnt.2006.06.003 ). Bu iki teoremleri eşzamanlı genelleme için bkz bu egzersizi ders "sayılar teorisi giriş" den düzeltilmiş Vikiversite üzerinde .
-
Pascal Boyer, Sayıların ve uygulamalarının küçük arkadaşı , Paris, Calvage ve Mounet,2019, 648 s. ( ISBN 978-2-916352-75-6 ) , ℤ Aritmetiği, bölüm. I.3.2 ("İkinci dereceden artıklar: uygulamalar"), s. 47-49.
-
Aritmetik ilerleme teoremi olmayan bir ispat için bkz. ( N ∈ ℕ için) İrlanda ve Rosen 1990 , s. 57-58 (böl. 5, § 2, inci. 3) ya da ( n ∈ ℤ) bu düzeltilmiş atama ders “sayı teorisi Giriş” den Vikiversite ile .
-
İlgili konularda, bkz. " Teorem Grunwald-Wang " ve (in) " Kare olmayan bir sayı var mı qui, her primin ikinci dereceden kalıntısıdır? » , MathOverflow'da .
-
Daha açık bir şekilde, görece asimptotik yoğunluk D çözeltilerinin sonsuz setinin (asal sayıların kümesindeki) sıfır olmayan ve sadece ifade edilebilir: kolayca (çıkartılarak azaltmak S burada hiçbir durumda gereksiz öğeleri) S'nin elemanlarının çarpımı , boş çarpımdan ayrı bir karedir ve o zaman, D = 2 - | S | , aritmetik ilerleme teoreminin kantitatif versiyonunu kullanarak : bkz. Wright 2016 (th. 4.9) veya (en) R. Balasubramanian (en) , F. Luca ve R. Thangadurai, “ Tam derece üzerinde ” , Proc. Acı. Matematik. Soc. , cilt. 138,p{\ displaystyle p}
Q(-de1,-de2,...,-deℓ){\ 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 )veya daha önce bahsedilen Wikiversity'de düzeltilen alıştırmanın kanıtı (çok daha basit) .
Ayrıca görün
İlgili Makaleler
Dış bağlantılar
- (tr) Eric W. Weisstein , " İkinci Dereceden Kalıntı " , MathWorld'de
- (tr) Walter D. Stangl , " ℤ n'deki Kareleri Sayma " , Math. Mag. , cilt. 69, n, o , 4,1996, s. 285-289 ( çevrimiçi okuyun )
-
CF Gauss , Aritmetik Araştırma ( çevrimiçi okuyun ), § 101 ve 102
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">