Rozkład na czynniki pierwsze, nietrywialny pierwiastek z 1

Heniek1991 · Post autor: **Heniek1991** » 6 maja 2011, o 11:54

Mam pytanie do takiego zadania:

Wiedząc, że liczba n=3598057 jest iloczynem dwóch różnych liczb pierwszych oraz że liczba 20779 jest pierwiastkiem z 1 modulo n, znajdź rozkład n na czynniki pierwsze.

Nie bardzo wiem co wynika z faktu, że \(\displaystyle{ 20778*20780 \equiv 0 \ mod \ n}\).

Xitami · Post autor: **Xitami** » 6 maja 2011, o 21:24

\(\displaystyle{ 1^2\equiv 20779^2\\\\
gcd(20779-1, n)=3463\\\\
\frac{n}{3463}=1039}\)

Maurice Kraitchik... (20)