Znajdź wszystkie pierwiastki pierwotne liczby 25

[urchin]

Problem jak to zrobić: Znajdź wszystkie pierwiastki pierwotne liczby 25

[ben2109]

\(\displaystyle{ k^{1}+ k^{2}+ k^{3}+ k^{4}...+k^{20}\equiv 0 \pmod{25}}\)

Oczywiście każde \(\displaystyle{ k^{l}}\) ma inną resztę, która jest względnie pierwsza z \(\displaystyle{ 25}\).

Jeżeli \(\displaystyle{ k}\) jest pierwiastkiem pierwotnym \(\displaystyle{ mod 25}\), to dla każdego \(\displaystyle{ n \in N}\) , takiego że \(\displaystyle{ (n, 24)=1}\) \(\displaystyle{ n \in \left( 0;25\right)}\) , liczba \(\displaystyle{ k^{n}}\) również jest pierwiastkiem.



Jeżeli \(\displaystyle{ k}\) jest pierwiastkiem pierwotnym to:
\(\displaystyle{ k^{4} \equiv 1 \pmod{5}}\)
\(\displaystyle{ k^{4} \not\equiv 1 \pmod{25}}\)

Zauważ, że jeśli \(\displaystyle{ k\equiv a \pmod{25}}\) jest pierwiastkiem, to \(\displaystyle{ k\equiv 25-a \pmod{25}}\) również nim jest, czyli mniej sprawdzania.

[urchin]

Dzięki za odpowiedź, chociaż nadal nie rozumiem tego.
Z definicji z Wiki zrozumiałem że dana liczba ma pierwiastek pierwotny jeśli reszta z modulo pierwiastka i kolejnych potęg tego pierwiastka z tą liczbą daje wszystkie reszty tj.

np. dla 13, pierwiastkiem pierwotnym jest 2
Mod(2,13) i z kolejnymi potęgami 2,4,8,16,32...itd.
daje reszty: 2 4 8 3 6 12 11 9 5 10 7 1

Wydaje mi się że 25 nie ma pierwiastka pierwotnego?

[ben2109]

-----> Czyli odpadają nam 5,10,15,20,25. Czyli reszt z dzielenia jest \(\displaystyle{ 20}\), dlatego \(\displaystyle{ k}\) jest tam do dwudziestych potęg.

-Rozdział pierwiastki pierwotne dla modułu \(\displaystyle{ p^{2}}\)

A dokładniej przykład, który tam jest. Ogólnie symbol \(\displaystyle{ \phi (n)}\) oznacza ilość liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\) względnie pierwszych z \(\displaystyle{ n}\).

[urchin]

Bardzo dziękuję

Pozdrawiam