Eulers sætning (talteori)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 6. maj 2022; verifikation kræver 1 redigering .

Eulers sætning i talteori siger:

Hvis og er coprime , hvor er Euler-funktionen så . $-en$ $m$ $a^{\varphi(m)} \equiv 1 \pmod m$ $\varphi(m)$

En vigtig konsekvens af Eulers sætning for tilfældet med et primmodul er Fermats lille sætning :

Hvis det ikke er deleligt med et primtal , så . $-en$ $s$ $a^{{p-1}}\equiv 1{\pmod p}$

Til gengæld er Eulers sætning en konsekvens af den generelle algebraiske Lagrange-sætning , anvendt på det reducerede system af rester modulo . $m$

Beviser

Brug af talteori

Lad være alle distinkte naturlige tal mindre og relativt prime til det. $x_1, \dots, x_{\varphi(m)}$ $m$

Overvej alle mulige produkter for alle fra til . $x_i a$ $jeg$ $en$ $\varphi(m)$

Da det er coprime med , og coprime med , så er det også coprime med , altså for nogle . $-en$ $m$ $x_{i}$ $m$ $x_i a$ $m$ $x_i a \equiv x_j\pmod m$ $j$

Bemærk, at alle rester, når de divideres med , er forskellige. Ja, selv om det ikke er tilfældet, så er der sådanne $x_i a$ $m$ $i_1\neq i_2$

x_{i_1} a \equiv x_{i_2} a\pmod m

eller

(x_{i_1} - x_{i_2}) a \equiv 0\pmod m.

Siden coprime med , svarer den sidste lighed til det faktum, at $-en$ $m$

x_{i_1} - x_{i_2} \equiv 0\pmod m

eller .

x_{i_1} \equiv x_{i_2}\pmod m

Dette modsiger det faktum, at tallene er parvis forskellige modulo . $x_1, \dots, x_{\varphi(m)}$ $m$

Vi multiplicerer alle sammenligninger af formen . Vi får: $x_i a \equiv x_j\pmod m$

x_1 \cdots x_{\varphi(m)} a^{\varphi(m)} \equiv x_1 \cdots x_{\varphi(m)}\pmod m

eller

x_1 \cdots x_{\varphi(m)} (a^{\varphi(m)}-1) \equiv 0\pmod m

Da tallet er coprime med , svarer den sidste sammenligning til, at $x_1 \cdots x_{\varphi(m)}$ $m$

a^{\varphi(m)}-1 \equiv 0\pmod m

eller

a^{\varphi(m)} \equiv 1\pmod m.

■

Ved hjælp af gruppeteori

Overvej den multiplikative gruppe af inverterbare elementer $\mathbb Z_n^*$ i restringen . Dens rækkefølge er ens i henhold til definitionen af Euler-funktionen . Da tallet er coprime med , er det tilsvarende element i inverterbart og tilhører . Elementet genererer en cyklisk undergruppe, hvis rækkefølge, ifølge Lagranges sætning , deler , dermed . ■ $\mathbb Z_n$ $\varphi (n)$ $-en$ $n$ $\overline a$ $\mathbb Z_n$ $\mathbb Z_n^*$ $\overline{a}\in \mathbb Z_n^*$ $\varphi (n)$ $\overline a^{{\varphi (n)}}=\overline 1$

Se også

Liste over objekter opkaldt efter Leonhard Euler

Litteratur

Ireland K., Rosen M. En klassisk introduktion til moderne talteori. — M .: Mir, 1987.

Eulers sætning (talteori)

Beviser

Brug af talteori

Ved hjælp af gruppeteori

Se også

Litteratur

Links