Euler-kritérium

A matematika és pontosabban moduláris aritmetika , Euler kritériuma egy tétel használt számos elméletet annak meghatározására, hogy egy adott egész szám, egy kvadratikus maradék modulo egy prímszám .

Államok

Legyen 2-től eltérő prímszám és egész szám a -val . $o$ $nál nél$ $o$

Ha van egy modulo másodfokú maradék , akkor . $nál nél$ $o$ ${\ displaystyle a ^ {\ frac {p-1} {2}} \ equiv 1 {\ pmod {p}}}$
Ha nem modulo másodfokú maradék, akkor . $nál nél$ $o$ ${\ displaystyle a ^ {\ frac {p-1} {2}} \ equiv -1 {\ pmod {p}}}$

Amit a Legendre szimbólumával lehet összefoglalni :

{\ displaystyle a ^ {\ frac {p-1} {2}} \ equiv \ balra ({\ frac {a} {p}} \ jobbra) {\ pmod {p}}}

A bizonyítás Fermat kis tételén és azon a tényen alapul, hogy egy integrális gyűrűben a polinomnak soha nem több a gyökere, mint a mértéke .

Példák

1. példa: megtalálni a prímszámokat modulo, amely egy egy négyzet

Legyen a = 17. Modulo melyik p (2-től és 17-től eltérő) prímszám ez a 17-es négyzet négyzet?

Az előző képlettel tesztelhetjük a p prímszámokat igény szerint. Például :

modulo 3, 17 (3 - 1) / 2 = 17 1 ≡ −1 van; ezért a 17 nem modulo 3 négyzet.
modulo 13, 17 (13 - 1) / 2 × 4 6 = (4 2 ) 3 × 3 3 × 1; ezért a 17 egy modulo 13 négyzet.

Azonban:

ezeket a számításokat sokkal gyorsabban elvégezhetjük moduláris aritmetika segítségével:
- modulo 3, 17 ≡ −1 nem négyzet, az egyetlen nulla nélküli négyzet (± 1) 2 = 1,
- modulo 13, 17 ≡ 4 = 2 2 ;
a teljes válaszhoz a másodfokú kölcsönösségi törvényhez kell folyamodni : p > 2 prímszám esetén (17 / p ) = 1 akkor és csak akkor, ha a 17 modulo, p ± 1, ± 2, ± 4 vagy ± 8. Így :
- 17 egy négyzet alakú modulo 13, 19, 43, 47, ...
- A 17 nem modulo 3, 5, 7, 11, 23, ...

2. példa: megtalálni a négyzetek modulo adott prímszám p .

Mi a modulo 17 négyzet?

Kiszámíthatjuk őket:

(± 1) 2 = 1 (± 2) 2 = 4 (± 3) 2 ≡ –8 (17. mod) (± 4) 2 ≡ –1 (17. módosítás) (± 5) 2 × 8 (17. módosítás) (± 6) 2 × 2 (17. módosítás) (± 7) 2 ≡ –2 (17. mód) (± 8) 2 ≡ –4 (17. mód)

Tehát a modulo 17 8 nem nulla négyzet ± 1, ± 2, ± 4 és ± 8.

Annak megismeréséhez, hogy egy szám másodfokú maradék-e, megnézhetjük, hogy szerepel-e (17-es modulo) a listában, vagy tesztelhetjük-e az Euler-kritérium alapján. Annak tesztelésére, hogy 2 modulo 17 négyzet-e, kiszámítjuk a 2 (17 - 1) / 2 = 2 8 ≡ 4 4 ≡ (–1) 2 ≡ 1 (mod 17) értékeket, tehát 2 másodfokú maradék. Annak teszteléséhez, hogy 3 modulo 17 négyzet-e, kiszámítjuk 3 (17 - 1) / 2 = 3 8 ≡ (–8) 4 ≡ (–4) 2 ≡ −1 (mod 17), tehát a 3 nem másodfokú maradék .

Általánosítás

Az Euler által megfogalmazott kritérium valójában általánosabb:

Legyen p = 1 + mn prímszám. Egy egész szám egy nem osztható által p egy n-edik teljesítmény mod p , ha (és csak akkor, ha) egy m ≡ 1 mod p .

A bizonyítás ugyanazokat az érveket használja, mint az n = 2 esetben ( lásd fent ). Euler először bebizonyítja Fermat kis tételét ( n = 1 eset ). Azt is észreveszi, hogy bármely r egész szám esetén , ha r 2 ≡ 1 mod p, akkor r ≡ ± 1 mod p . Alkalmazott, hogy r = egy ( p - 1) / 2 (a p ≠ 2), ez a megjegyzés befejezi a kritérium abban az esetben n = 2: ha egy nem négyzet mod p , nem csak R nem kongruens 1, de –1-vel egybevágó.

Megjegyzések és hivatkozások

(fr) Ez a cikk részben vagy egészben venni a Wikipedia cikket angolul című „ Euler kritériuma ” ( lásd a szerzők listáját ) .

Vagyis ha van olyan egész szám , hogy . $k$ ${\ displaystyle a \ equiv k ^ {2} {\ pmod {p}}}$
Például, lásd (a) William J. LeVeque (a) , Fundamentals of Number Theory , Dover ,1996( 1 st szerk. 1977) ( olvasható online ) , p. 68-69vagy „Euler-kritérium” a „Bevezetés a számelméletbe” leckében a Wikegyetemről .
Euler itt a véges különbség módszerét használja, mint a két négyzet tétel bizonyításában , mert még nem tudta, hogy a modulo prímszám, az r fok kongruenciájának legfeljebb r megoldása van. Lagrange ezt 1770 végén, 1771 elején mutatta be neki. (En) André Weil , Számelmélet: megközelítés a történelem folyamán Hammurapitól a Legendre-ig [ a kiadások részlete ], P. 198 .
(La) L. Euler, „ Theoremata circa residua ex Divisione potestatum relicta ” , Novi Comment. Acad. Sci. Manó. Petrop. , vol. 7,1761, P. 49–82 ( online olvasás )( E262 , 1755-ben írták és 1758-ban mutatták be ).
Lásd például a "Bevezetés a számelméletbe" lecke ezt a javított gyakorlatát a Wikiverzióról .
Azzal az érveléssel, amely - abban az időben, amikor a csoport fogalma még nem alakult ki - előrevetíti Lagrange tételét a csoportokról .
Ha p osztja r 2 - 1 = ( r + 1) ( r - 1), akkor a két tényező egyikét osztja.

Kapcsolódó cikkek

Euler kritériumát használják az Euler-Jacobi álprím számok meghatározásában .
Véges mező szintje