Eulerovo kritérium
V matematiky a přesněji v modulární aritmetice , Eulerova kritériem je věta použity v počtu teoreticky k určení, zda vzhledem k celé číslo je kvadratický zbytek modulo je prvočíslo .
Státy
Dovolit je prvočíslo jiné než 2 a prime integer s .
p{\ displaystyle p}
na{\ displaystyle a}
p{\ displaystyle p}![p](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36)
- Pokud je modulo kvadratický zbytek , pak .na{\ displaystyle a}
p{\ displaystyle p}
nap-12≡1(modp){\ displaystyle a ^ {\ frac {p-1} {2}} \ equiv 1 {\ pmod {p}}}![{\ displaystyle a ^ {\ frac {p-1} {2}} \ equiv 1 {\ pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61c57298af036683f635d0ccad0739bf49ecca04)
- Pokud to není modulo kvadratický zbytek, pak .na{\ displaystyle a}
p{\ displaystyle p}
nap-12≡-1(modp){\ displaystyle a ^ {\ frac {p-1} {2}} \ equiv -1 {\ pmod {p}}}![{\ displaystyle a ^ {\ frac {p-1} {2}} \ equiv -1 {\ pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0bc97ae7d788975dba5d1c3dc7204eb867435d0)
Které lze shrnout pomocí symbolu Legendre pomocí:
nap-12≡(nap)(modp){\ displaystyle a ^ {\ frac {p-1} {2}} \ equiv \ left ({\ frac {a} {p}} \ right) {\ pmod {p}}}![{\ displaystyle a ^ {\ frac {p-1} {2}} \ equiv \ left ({\ frac {a} {p}} \ right) {\ pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ac9cc90ec04277b58546ace9a694a17bc4b1412)
.
Důkaz je založen na Fermatově malé větě a na skutečnosti, že v integrálním kruhu polynom nikdy nemá více kořenů než jeho stupeň .
Příklady
Příklad 1: Najděte prvočísla modulo, které a je čtverec
Nechť a = 17. Modulo, která prvočísla p (jiná než 2 a 17) je toto číslo 17 čtverec?
Můžeme otestovat podle předchozího vzorce prvočísla p na vyžádání. Například :
- modulo 3, máme 17 (3 - 1) / 2 = 17 1 ≡ −1; 17 tedy není modulo 3 square.
- modulo 13, máme 17 (13 - 1) / 2 ≡ 4 6 = (4 2 ) 3 ≡ 3 3 ≡ 1; 17 je tedy modulo 13 čtverečních.
Nicméně:
- můžeme tyto výpočty provádět mnohem rychleji pomocí modulární aritmetiky:
- modulo 3, 17 ≡ −1 není čtverec, jediný nenulový čtverec je (± 1) 2 = 1,
- modulo 13, 17 ≡ 4 = 2 2 ;
- pro úplnou odpověď je nutné odvolat se na zákon kvadratické reciprocity : pro prvočíslo p > 2, (17 / p ) = 1 právě tehdy, když je modulo 17, p shodné s ± 1, ± 2, ± 4 nebo ± 8. Tak :
- 17 je čtvercový modulo 13, 19, 43, 47, ...
- 17 není modulo 3, 5, 7, 11, 23, ...
Příklad 2: Najděte čtverce modulo dané prvočíslo p .
Co jsou čtverce modulo 17?
Můžeme je vypočítat:
(± 1) 2 = 1
(± 2) 2 = 4
(± 3) 2 ≡ –8 (mod 17)
(± 4) 2 ≡ –1 (mod 17)
(± 5) 2 ≡ 8 (mod 17)
(± 6) 2 ≡ 2 (mod 17)
(± 7) 2 ≡ –2 (mod 17)
(± 8) 2 ≡ –4 (mod 17)
Takže 8 nenulových čtverců modulo 17 je ± 1, ± 2, ± 4 a ± 8.
Chcete-li zjistit, zda je číslo kvadratickým zbytkem, můžete se podívat, zda je v seznamu (modulo 17), nebo jej otestovat podle Eulerova kritéria. Chcete-li otestovat, zda 2 je čtverec modulo 17, spočítáme 2 (17 - 1) / 2 = 2 8 ≡ 4 4 ≡ (–1) 2 ≡ 1 (mod 17), takže 2 je kvadratický zbytek. Abychom otestovali, zda 3 je čtverec modulo 17, počítáme 3 (17 - 1) / 2 = 3 8 ≡ (–8) 4 ≡ (–4) 2 ≡ −1 (mod 17), takže 3 není kvadratický zbytek .
Zobecnění
Kritérium uvedené Eulerem je ve skutečnosti obecnější:
Nechť p = 1 + mn je prvočíslo. Celé číslo není dělitelný které p je n-tý síla mod p , pokud (a pouze v případě,) m ≡ 1 mod p .
Důkaz používá stejné argumenty jako v případě n = 2 ( viz výše ). Euler nejprve dokazuje Fermatovu malou větu (případ n = 1). Také si všimne, že pro každé celé číslo r , pokud r 2 ≡ 1 mod p, pak r ≡ ± 1 mod p . Použije-li se na r = a ( p - 1) / 2 (pro p this 2), tato poznámka splňuje své kritérium v případě n = 2: pokud a není čtvercový mod p , nejen r není shodný s 1, ale je shodný s –1.
Poznámky a odkazy
(fr) Tento článek je částečně nebo zcela převzat z článku Wikipedie v
angličtině s názvem
„ Eulerovo kritérium “ ( viz seznam autorů ) .
-
To znamená, že v případě, že je celé číslo takové, že .k{\ displaystyle k}
na≡k2(modp){\ displaystyle a \ equiv k ^ {2} {\ pmod {p}}}
-
Například viz (in) William J. LeVeque (in) , Základy teorie čísel , Dover ,1996( 1 st ed. 1977) ( číst on-line ) , str. 68-69nebo „Eulerovo kritérium“ v lekci „Úvod do teorie čísel“ na Wikiversity .
-
Euler zde používá svoji metodu konečných rozdílů jako ve svém důkazu věty o dvou čtvercích , protože ještě nevěděl, že modulo prvočíslo, kongruence stupně r má nanejvýš řešení r . Lagrange ho na to upozornil na konci roku 1770 - začátek roku 1771. (en) André Weil , The Number Number: The approach through history from Hammurapi to Legendre [ detail of the Edition ], str. 198 .
-
(La) L. Euler, „ Theoremata circa residua ex divisione potestatum relicta “ , komentář Novi. Acad. Sci. Imp. Petrop. , sv. 7,1761, str. 49-82 ( číst online )( E262 , napsáno v roce 1755 a předloženo v roce 1758 ).
-
Viz například toto opravené cvičení lekce „Úvod do teorie čísel“ na Wikiversity .
-
Zdůvodněním, které - v době, kdy se pojem skupiny ještě neobjevil - předznamenává Lagrangeovu teorém o skupinách .
-
Pokud p dělí r 2 - 1 = ( r + 1) ( r - 1), dělí jeden ze dvou faktorů.
Související články
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">