Pierwiastki pierwotne

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Awatar użytkownika
Poszukujaca
Użytkownik
Użytkownik
Posty: 2775
Rejestracja: 21 maja 2012, o 23:32
Płeć: Kobieta
Podziękował: 1019 razy
Pomógł: 165 razy

Pierwiastki pierwotne

Post autor: Poszukujaca » 20 paź 2017, o 09:35

Jak szybko znaleźć wszystkie pierwiastki pierwotne dla dużych liczb modulo? Na przykład dla \(\displaystyle{ m=11^{2}}\)?

Mogę skorzystać z twierdzenia, że jeżeli \(\displaystyle{ r}\) jest pierwiastkiem pierwotnym modulo \(\displaystyle{ p}\), to \(\displaystyle{ r}\) lub \(\displaystyle{ p+r}\) jest pierwiastkiem pierwotnym dla \(\displaystyle{ p^{2}}\).

Ale to i tak nie za wiele mi pomoże.

Wszystkich pierwiastków pierwotnych modulo \(\displaystyle{ 121}\) jest aż \(\displaystyle{ \varphi (\varphi(121))=\varphi(110)=40}\).

Mogę znaleźć pierwiastki pierwotne dla \(\displaystyle{ m =11}\) i istotnie są to liczby \(\displaystyle{ 2,6,7,8}\) w związku z tym pierwiastkami pierwotnymi dla \(\displaystyle{ m=121}\) mogą być liczby \(\displaystyle{ 2,6,7,8,13,17,18,19}\), ale to tylko osiem możliwych pierwiastków. Jak znaleźć pozostałe bez liczenia rzędów kolejnych liczb?

ODPOWIEDZ