Články

3.3: Multiplikatívny poriadok a aplikácie - matematika


V tejto časti dokazujeme dva veľmi užitočné výsledky, ktoré sa nazývajú Eulerova veta a Fermatova malá veta (špeciálny prípad Eulerovej). Nesledujeme dôkaznú stratégiu Eulera a Fermata, namiesto toho používame prístup inšpirovaný abstraktnou algebrou a Lagrangeovou vetou v danom predmete.

Najprv potrebujeme

[def: multorder] Predpokladajme, že (n v NN ) a (a v ZZ ) vyhovujú (n ge2 ) a ( gcd (a, n) = 1 ). Potom definujeme multiplikatívne poradie (a ) v režime (n ) (nazýva sa iba objednať keď multiplikatívne a (n ) možno chápať z kontextu) ako najmenšie (k v NN ) také, že (a ^ k equiv1 pmod {n} ). Poradie (a ) v režime (n ) je napísané ( ord_n (a) ).

Poďme si overiť niečo, čo by malo byť pravdepodobne vždy skontrolované na novú definíciu:

[prop: orderwelldefined] Vzhľadom na relatívne prvočísla (n v NN ) a (a v ZZ ) s (n ge2 ), ( ord_n (a) ) je dobre definovaný .

Problém v definícii ( ord_n (a) ) môže spočívať v tom, že nemusí existovať vôbec žiadna hodnota (k v NN ), pre ktorú (a ^ k equiv1 pmod {n} ).

Ale všimnite si, že ide o kongruenciu, takže sa skutočne zaoberáme iba elementmi (a ^ k ) až po ich triedu kongruencie.

Takže sa pozrite na ( {[a ^ p] _n mid p in NN } ) a predstavte si, že dáte prirodzené čísla (p in NN ) do rôznych polí na základe príslušnej triedy kongruencie ([a ^ p] v ZZ / n ZZ ). Pretože v ( NN ) je nekonečne veľa prvkov a iba (n ) v ( ZZ / n ZZ ) - (n ) škatule - podľa Pigeonholeho princípu (veta [thm: pigeonhole]) musia existovať dve (v skutočnosti nekonečne veľa párov) rôznych hodnôt (p, q v NN ) také, že (p ) a (q ) skončiť v rovnakom poli, čo znamená ([a ^ p] = [a ^ q] ). Predpokladajme bez straty všeobecnosti, že (p> q ), teda (p-q v NN ).

Je nám dané, že ( gcd (a, n) = 1 ), takže v dôsledku toho [Cor: modinv] existuje (a ^ {- 1} ) v mod (n ). Teda [a ^ {pq} ekviv a ^ p , (a ^ {- 1}) ^ q ekviv a ^ q , (a ^ {- 1}) ^ q ekviv a ^ 0 ekviv1 pmod {n} ] (nahradenie (a ^ p ) za (a ^ q ) uprostred tejto kongruencie, pretože vieme, že ([a ^ p] = [a ^ q] ), ktoré znamená (a ^ p equiv a ^ q pmod {n} )), a preto množina (k v NN ), pre ktorú (a ^ k equiv1 pmod {n} ) neprázdny. Poradie je najmenšia takáto hodnota, ktorá existuje podľa princípu objednávania.

Tu je veta z abstraktnej algebry (Lagrangeova veta) preložená do súčasného kontextu:

[thm: orddividesphi] Vzhľadom na relatívne prvočísla (n v NN ) a (a v ZZ ), ( ord_n (a) mid phi (n) ).

Začnite tým, že sa pozrieme na triedy zhody ([a], [a ^ 2], [a ^ 3] bodky ). Vystúpia až do ([a ^ { ord_n (a)}] = [1] ) a potom sa začnú opakovať, takže množina [ doľava = {[a ^ j] mid j in NN, j le ord_n (a) } ] je množina ( ord_n (a) ) prvkov ( ZZ / n ZZ ) (v teórii skupín to množina ( doľava ) sa nazýva cyklická podskupina (( ZZ / n ZZ) ^ * ) generovaná (a )). Všimnite si, že pretože (a ^ { ord_n (a)} equiv1 pmod {n} ), ([1] v zľava ). Tiež, pretože ak (a ^ {- 1} ) je inverzná hodnota (a ) mod (n ), ((a ^ {- 1}) ^ k ) je inverzná hodnota ( a ^ k ) pre (k v NN ), vidíme, že ( left subseteq ( ZZ / n ZZ) ^ * ).

Na záver ukážeme, že (( ZZ / n ZZ) ^ * ) je zložené z určitého počtu, povedzme (m ), kúskov, ktoré budeme nazývať kozety, z ktorých každý je bijektív s ( doľava ). Tieto kúsky teda budú mať všetky ( ord_n (a) ) prvky, takže (m cdot ord_n (a) = # left (( ZZ / n ZZ) ^ * right) = phi (n) ), z čoho vyplýva náš požadovaný výsledok.

A coset of ( left ) je množina tvaru [x doľava = {[x] cdot [a ^ j] = [x , a ^ j] stred j v NN, j le ord_n (a) } ] kde ([x] v ( ZZ / n ZZ) ^ * ). Zaznamenali sme, že ([1] in left ), takže ( forall [x] in ( ZZ / n ZZ) ^ * ), ([x] v x left ), čo znamená, že každá trieda zhody ([x] v ( ZZ / n ZZ) ^ * ) je v nejakej množine, t.j. [ ZZ / n ZZ subseteq bigcup _ {[x] in ( ZZ / n ZZ) ^ *} x doľava . ]

V skutočnosti je každý coset (x left ) bijektívny s ( left ). Bijekcia je mapa (f_x: doľava do x doľava ) definovaná (f_x ([a ^ j]) = [xa ^ j] ) pre (j in NN ) s (j le ord_n (a) ). Táto mapa je bijekciou, pretože má inverzný (f_ {x ^ {- 1}} ) pochádzajúci z inverzného režimu (n ) z (x ).

Teraz predpokladajme, že (x doľava ) a (y doľava ) sú dva kozety. Tvrdím, že buď ​​(x doľava = y doľava ) alebo (x doľava bigcap y doľava = emptyset ). Z tohto dôvodu predpokladajme (x doľava bigcap y doľava neq emptyset ), takže ( existuje [z] v x doľava bigcap y dolava ). To znamená, že ( existuje j, k v NN ) také, že (j le ord_n (a) ), (k le ord_n (a) ) a ([xa ^ j] = [z] = [ya ^ k] ). Inými slovami, [xa ^ j equiv ya ^ k pmod {n} . ] Bez straty všeobecnosti predpokladajme (j le k ). Ak potom vynásobíme obe strany vyššie uvedenej zhody znakom ((a ^ {- 1}) ^ j ), máme (x equiv ya ^ {k-j} pmod {n} ). To však znamená, že každý prvok ([xa ^ p] in x left ) je možné vyjadriť ako ([ya ^ {p + kj}] in y left ) a každý prvok ([ya ^ q] in y zľava ) je možné vyjadriť ako ([xa ^ {q + jk}] x x zľava ). Teda (x doľava = y doľava ).

Bolo to veľa práce, ale teraz veľmi ľahko získame slávne vety Fermat’s Little a Euler.

[thm: eulers]Eulerova veta Povedzte (a v ZZ ) a (n v NN ) uspokojte ( gcd (a, n) = 1 ). Potom (a ^ { phi (n)} equiv1 pmod {n} ).

Predchádzajúca veta [thm: orddividesphi] nám povedala, že ( ord_n (a) mid phi (n) ), takže ( existuje m v ZZ ) také, že (m cdot ord_n (a) = phi (n) ). Podľa definície poradia to znamená [a ^ { phi (n)} equiv a ^ {m ord_n (a)} equiv left (a ^ { ord_n (a)} right) ^ m equiv1 ^ m equiv1 pmod {n}. ]

[cor: FLT]Fermatova malá veta Ak (p ) je prvočíslo a (a v ZZ ) vyhovuje ( gcd (p, a) = 1 ), potom (a ^ {p-1} equiv1 pmod {p} ).

Videli sme, že pre prvočísla (p ), ( phi (p) = p-1 ), takže tu treba urobiť veľmi málo.

Niekedy človek vidí Fermatovu malú vetu v nasledujúcej inej podobe:

[thm: altFLT] Ak (p ) je prvočíslo, potom ( forall a in ZZ ), (a ^ p equiv a pmod {p} ).

Ak ( gcd (a, p) = 1 ), potom pomocou Fermat’s Little, (a ^ {p-1} equiv1 pmod {p} ). Vynásobením obidvoch strán tejto kongruencie znakom (a ) získate požadovaný výsledok.

Ak namiesto ( gcd (a, p) neq1 ), musí to byť ( gcd (a, p) = p ), pretože tento gcd je deliteľom (p ), ktorý je prvočíslom. Gcd je tiež deliteľom (a ), takže v skutočnosti (p mid a ). Ale potom (a ) a všetky jeho sily sú kongruentné mod (p ) na (0 ), takže (a ^ p equiv0 equiv a pmod {p} ).

Cvičenia pre §3

Aký je zvyšok, keď (15! ) Sa vydelí (17 ) a zvyšok, keď (2 cdot (26!) ) Sa vydelí (29 )?

Vieme, že (17 ) je prvočíslo (je to len úžasné číslo, však?). Ale pre istotu to dokážte pomocou Wilsonovej vety.

Môžeme z Fermatovej Little Theorem postaviť test primality? Ak je to tak, bolo by to lepšie (efektívnejšie) ako to založené na Wilsonovej vete? Ako by to fungovalo? Napíšte jasné, formálne vyhlásenie k navrhovanému testu primality.

Ak ovládate programovací jazyk, napíšte nejaký kód a vyskúšajte svoj test primality. Pokiaľ nie (alebo v každom prípade po programovaní), urobte si malý prieskum, aby ste zistili, či už bola táto otázka vyšetrená, a ak áno, aký bol záver. Uveďte buď formálne vyhlásenie o teste a formálny výsledok popisujúci jeho účinnosť, alebo protiklad k testu, ktorý ste našli v literatúre.

Predpokladajme, že (p ) je nepárne prvočíslo. Dokážte, že ak má kvadratická zhoda (x ^ 2 + 1 equiv0 pmod {p} ) riešenie, potom (p equiv1 pmod {4} ). [Tip: Použite Fermatovu malú vetu na riešenie (a ) zhody, potom množte a vydelte (2 ) v moci.]


Pozri si video: Aplikácia eTIPOS číselné hry 2 (December 2021).