Matematyka.pl

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}\)

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.

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!