Wzmocnione twierdzenie Eulera

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Rodis
Użytkownik
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

Post autor: Rodis »

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}\)
Awatar użytkownika
Vax
Użytkownik
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

Post autor: Vax »

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.
Rodis
Użytkownik
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

Post autor: Rodis »

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!
ODPOWIEDZ