Euler-tétel (számelmélet)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. május 6-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Euler tétele a számelméletben ezt mondja:

Ha és a koprím , akkor hol van az Euler-függvény . $a$ $m$ $a^{\varphi(m)} \equiv 1 \pmod m$ $\varphi(m)$

Az Euler-tétel egyik fontos következménye a prímmodul esetére Fermat kis tétele :

Ha nem osztható prímszámmal , akkor . $a$ $p$ $a^{{p-1}}\equiv 1{\pmod p}$

Az Euler-tétel viszont az általános algebrai Lagrange-tétel következménye , amelyet a redukált maradékrendszerre alkalmazunk modulo . $m$

Bizonyíték

Számelmélet segítségével

Legyen minden különböző természetes szám kisebb és viszonylag prím hozzá. $x_1, \pontok, x_{\varphi(m)}$ $m$

Fontolja meg az összes lehetséges terméket mindenki számára től ig . $x_i a$ $én$ $egy$ $\varphi(m)$

Mivel koprím -val és -vel , akkor -val is koprím , azaz egyeseknél . $a$ $m$ $x_{i}$ $m$ $x_i a$ $m$ $x_i a \equiv x_j\pmod m$ $j$

Ne feledje, hogy az összes maradék , ha osztva van, különálló. Valóban, ha ez nem így van, akkor is vannak ilyenek $x_i a$ $m$ $i_1\neq i_2$

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

vagy

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

Mivel a koprím -val , az utolsó egyenlőség egyenértékű azzal, hogy $a$ $m$

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

vagy .

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

Ez ellentmond annak a ténynek, hogy a számok páronként különálló modulo . $x_1, \pontok, x_{\varphi(m)}$ $m$

Az űrlap összes összehasonlítását megszorozzuk . Kapunk: $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

vagy

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

Mivel a szám koprím és -vel , az utolsó összehasonlítás egyenértékű azzal, hogy $x_1 \cdots x_{\varphi(m)}$ $m$

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

vagy

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

■

A csoportelmélet segítségével

Tekintsük a maradékgyűrű invertálható elemeinek multiplikatív csoportját $\mathbb Z_n^*$ . Sorrendje az Euler-függvény definíciója szerint egyenlő . Mivel a szám koprím -vel , a megfelelő elem invertálható és a -hoz tartozik . Az elem egy ciklikus részcsoportot generál, amelynek sorrendje Lagrange tétele szerint osztja , tehát . ■ $\mathbb Z_n$ $\varphi (n)$ $a$ $n$ $\overline a$ $\mathbb Z_n$ $\mathbb Z_n^*$ $\overline{a}\in \mathbb Z_n^*$ $\varphi (n)$ $\overline a^{{\varphi (n)}}=\overline 1$

Lásd még

Leonhard Eulerről elnevezett objektumok listája

Irodalom

Ireland K., Rosen M. Klasszikus bevezetés a modern számelméletbe. - M .: Mir, 1987.

Linkek

Témák: Euler-tétel, Kínai maradék tétel , Amir Kamil, CS70, 2003. ősz. UC Berkeley
RSA és a kínai maradék tétel / Discrete Mathematics for CS 12. előadás, Wagner, CS70, 2003. ősz. UC Berkeley