Eulerova věta (aritmetická)
V matematice je věta z Euler nebo Euler-Fermatova v modulární aritmetice , publikoval v roce 1761 podle matematik švýcarské Leonhard Euler , zní:
Pro jakékoliv celé číslo n > 0 a jakékoliv celé číslo z nejlepších s n (jinými slovy: invertibilní mod n ),
naφ(ne)≡1(modne){\ displaystyle a ^ {\ varphi (n)} \ equiv 1 {\ pmod {n}}}
kde φ je Eulerova indikátorová funkce a mod označuje kongruenci s celými čísly .
Tato věta je zobecněním Fermatovy malé věty, která se zabývá pouze případem, kdy n je prvočíslo .
To znamená, že exponent λ ( n ) (nazvaný Carmichael indikatrix z n ) ze skupiny (ℤ / n ℤ) x z invertibles v kruhu ℤ / n ℤ je dělitel v pořadí cp ( n ) této skupiny (tato vlastnost, společná všem konečným skupinám , je odvozena z Lagrangeovy věty o skupinách ).
Umožňuje modulo n napájecí redukce . Například, pokud chceme najít číslici jednotek 7 222 , to znamená najít, ke kterému číslu mezi 0 a 9 odpovídá shodná 7 222 modulo 10, stačí vidět, že mezi nimi je prvočíslo 7 a 10 a že φ (10) = 4 . Eulerova věta nám to tedy říká
74≡1(mod10).{\ displaystyle 7 ^ {4} \ equiv 1 {\ pmod {10}}.}
Dedukujeme to
7222≡74×55+2≡(74)55×72≡155×72≡49≡9(mod10).{\ displaystyle 7 ^ {222} \ equiv 7 ^ {4 \ krát 55 + 2} \ equiv (7 ^ {4}) ^ {55} \ krát 7 ^ {2} \ equiv 1 ^ {55} \ krát 7 ^ {2} \ equiv 49 \ equiv 9 {\ pmod {10}}.}
Hledaný počet je tedy 9.
Další ukázka
Existuje mnoho důkazů o této větě. Již jsme poskytli to, co zobecňuje důkaz Fermatovy malé věty Lagrangeovou teorémou . Můžeme také zobecnit základní aritmetický důkaz :
Nechť n > 0 a a je celé číslo prime s n . Poznámka třídu modulo celého čísla , zejména .
na¯{\ displaystyle {\ overline {a}}}
ne{\ displaystyle n}
na{\ displaystyle a}
na¯∈(Z/neZ)×{\ displaystyle {\ overline {a}} \ in \ left (\ mathbb {Z} / n \ mathbb {Z} \ right) ^ {\ times}}![{\ displaystyle {\ overline {a}} \ in \ left (\ mathbb {Z} / n \ mathbb {Z} \ right) ^ {\ times}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/700c6531f00f82ca13f3b3d3cdcfe5c0878701b7)
Bijekce umožňuje přepsat produkt :
(Z/neZ)×→(Z/neZ)×,X↦na¯X{\ displaystyle \ left (\ mathbb {Z} / n \ mathbb {Z} \ right) ^ {\ times} \ doleva (\ mathbb {Z} / n \ mathbb {Z} \ right) ^ {\ times }, \; x \ mapsto {\ overline {a}} x}
P: =∏X∈(Z/neZ)×X{\ displaystyle P: = \ prod _ {x \ in \ left (\ mathbb {Z} / n \ mathbb {Z} \ right) ^ {\ times}} x}![{\ displaystyle P: = \ prod _ {x \ in \ left (\ mathbb {Z} / n \ mathbb {Z} \ right) ^ {\ times}} x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a1af3902c4d73f4469e5123df494d22bc31311a)
P=∏X∈(Z/neZ)×(na¯X)=na¯Kartu((Z/neZ)×)P=na¯φ(ne)P{\ displaystyle P \; = \ prod _ {x \ in \ left (\ mathbb {Z} / n \ mathbb {Z} \ right) ^ {\ times}} \ left ({\ overline {a}} x \ right) = \; {\ overline {a}} ^ {\ operatorname {Card} \ left (\ left (\ mathbb {Z} / n \ mathbb {Z} \ right) ^ {\ times} \ right)} P \; = {\ overline {a}} ^ {\ varphi (n)} P}![{\ displaystyle P \; = \ prod _ {x \ in \ left (\ mathbb {Z} / n \ mathbb {Z} \ right) ^ {\ times}} \ left ({\ overline {a}} x \ right) = \; {\ overline {a}} ^ {\ operatorname {Card} \ left (\ left (\ mathbb {Z} / n \ mathbb {Z} \ right) ^ {\ times} \ right)} P \; = {\ overline {a}} ^ {\ varphi (n)} P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71803a19810a6c33b16bacb504252ce037c77af8)
.
Zakončíme zjednodušením pomocí invertible :
P{\ displaystyle P}![P](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a)
1¯=na¯φ(ne)=naφ(ne)¯{\ displaystyle {\ overline {1}} = {\ overline {a}} ^ {\ varphi (n)} = {\ overline {a ^ {\ varphi (n)}}}}![{\ displaystyle {\ overline {1}} = {\ overline {a}} ^ {\ varphi (n)} = {\ overline {a ^ {\ varphi (n)}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/449ef1d0f9d2b784edc9531c207b4c07907f9b6d)
.
Odkaz
-
(La) L. Euler, „ Theoremata arithmetica nova methodo demonstrata “ , komentář Novi. Acad. Sci. Imp. Petrop. , sv. 8,1763, str. 74-104 ( číst online )( E271 , napsáno v roce 1758 a předloženo v roce 1760 ).
Související článek
Multiplikativní objednávka
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">