Wzmocnione twierdzenie Eulera
-
- Użytkownik
- Posty: 23
- Rejestracja: 25 lut 2009, o 21:22
- Płeć: Mężczyzna
- Podziękował: 1 raz
- Pomógł: 1 raz
Wzmocnione twierdzenie Eulera
Dany jest rozkład na liczby pierwsze \(\displaystyle{ n={p_1}^{e_1} \cdot \ldots \cdot {p_k}^{e_k}}\), oraz \(\displaystyle{ \lambda(n) = NWW(\phi({p_1}^{e_1}), \ldots, \phi({p_k}^{e_k}))}\), gdzie \(\displaystyle{ \phi}\) to funkcja Eulera. Wykaż, że jeśli \(\displaystyle{ NWD(a, n) = 1}\), to \(\displaystyle{ a^{\lambda(n)} \equiv 1 \mod n}\)
- Vax
- Użytkownik
- Posty: 2913
- Rejestracja: 27 kwie 2010, o 22:07
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska / Warszawa
- Podziękował: 4 razy
- Pomógł: 612 razy
Wzmocnione twierdzenie Eulera
Z chińskiego twierdzenia o resztach mamy:
\(\displaystyle{ a^{\lambda(n)} \equiv 1\pmod{n} \\ \\ \iff \\ \\ \begin{cases} a^{\lambda(n)} \equiv 1\pmod{p_1^{e_1}}\\ a^{\lambda(n)} \equiv 1\pmod{p_2^{e_2}} \\ ... \\ a^{\lambda(n)} \equiv 1\pmod{p_k^{e_k}} \end{cases}}\)
Ale z założenia dla pewnego \(\displaystyle{ k\in \mathbb_{Z_+}}\) dostajemy \(\displaystyle{ \lambda(n) = k\cdot \phi(p_1^{e_1})}\), więc pierwsza kongruencja jest równoważna:
\(\displaystyle{ a^{k\cdot \phi(p_1^{e_i})} \equiv 1\pmod{p_1^{e_1}} \Leftrightarrow \left(a^{\phi(p_1^{e_1})}\right)^k \equiv 1\pmod{p_1^{e_1}}}\)
A to z twierdzenia Eulera jest równoważne \(\displaystyle{ 1 \equiv 1\pmod{p_1^{e_1}}}\)
Analogicznie pokazujemy prawdziwość pozostałych kongruencji, qed.
\(\displaystyle{ a^{\lambda(n)} \equiv 1\pmod{n} \\ \\ \iff \\ \\ \begin{cases} a^{\lambda(n)} \equiv 1\pmod{p_1^{e_1}}\\ a^{\lambda(n)} \equiv 1\pmod{p_2^{e_2}} \\ ... \\ a^{\lambda(n)} \equiv 1\pmod{p_k^{e_k}} \end{cases}}\)
Ale z założenia dla pewnego \(\displaystyle{ k\in \mathbb_{Z_+}}\) dostajemy \(\displaystyle{ \lambda(n) = k\cdot \phi(p_1^{e_1})}\), więc pierwsza kongruencja jest równoważna:
\(\displaystyle{ a^{k\cdot \phi(p_1^{e_i})} \equiv 1\pmod{p_1^{e_1}} \Leftrightarrow \left(a^{\phi(p_1^{e_1})}\right)^k \equiv 1\pmod{p_1^{e_1}}}\)
A to z twierdzenia Eulera jest równoważne \(\displaystyle{ 1 \equiv 1\pmod{p_1^{e_1}}}\)
Analogicznie pokazujemy prawdziwość pozostałych kongruencji, qed.
-
- Użytkownik
- Posty: 23
- Rejestracja: 25 lut 2009, o 21:22
- Płeć: Mężczyzna
- Podziękował: 1 raz
- Pomógł: 1 raz
Wzmocnione twierdzenie Eulera
Chyba nie widzę implikacji w lewo (pierwszej z góry), ale można ten sam efekt osiągnąć korzystając z faktu \(\displaystyle{ a|n \wedge b|n \wedge NWD(a,b) = 1 \Rightarrow ab | n}\), uogólnionego na wiele składników, podstawiając \(\displaystyle{ n = a^{\lambda(n)} - 1}\).
Dzięki!
Dzięki!