Pierwiastki pierwotne

[margolcia]

1 Wiedząc, że 2 jest pierwiastkiem pierwotnym mod 37 wypisać wszystkie (różne modulo 37) pierwiastki pierwotne modulo 37.

2 Wiedząc, że 2 jest pierwiastkiem pierwotnym modulo 37 oraz \(\displaystyle{ 7 ^{6}=26(mod37)}\)wyznaczyć wszystkie pierwiastki kongruencji \(\displaystyle{ x^{6}=26(mod37)}\).

[pawels]

2. Weźmy \(\displaystyle{ a,b}\), tekie że \(\displaystyle{ 2^a=7}\) i \(\displaystyle{ 2^b=x}\). Wówczas na mocy założeń mamy \(\displaystyle{ 2^{6a}=26=2^{6b}}\). Zauważmy, że \(\displaystyle{ 2^6}\) też jest pierwiastkiem pierwotnym. Wówczas mamy \(\displaystyle{ (2^6)^a=(2^6)^b}\), czyli \(\displaystyle{ a=b}\), czyli \(\displaystyle{ 7=2^a=2^b=x}\).

Pozwoliłem sobie pisać znak równosć zamiast przystawania modulo 37 (właściwie jest to równość w \(\displaystyle{ \mathbb{Z}_{37}}\) więc czemu nie).

[SaxoN]

W pierwszym korzystamy z tego, że jeżeli \(\displaystyle{ a}\) jest pierwiastkiem pierwotnym (wolę nazwę generator, jest bardziej szpanerska) modulo \(\displaystyle{ p}\), to dla każdego \(\displaystyle{ k\in\mathbb{N}}\) takiego, że \(\displaystyle{ (k, p-1)=1}\) liczba \(\displaystyle{ a^k}\) również jest generatorem.