\(\displaystyle{ p = 2q+1}\) jest liczbą pierwszą, gdzie \(\displaystyle{ q}\) - liczba pierwsza nieparzysta.
\(\displaystyle{ a}\) jest liczbą całkowitą taką, że \(\displaystyle{ a^3 - a \not\equiv 0 \mod p}\).
Pokazać, że \(\displaystyle{ a}\) lub \(\displaystyle{ -a}\) jest generatorem multiplikatywnym \(\displaystyle{ \mod p}\)
Witam i bardzo proszę o pomoc, pozdrawiam.
Liczba pierwsza p = 2q + 1 a generator grupy mod p
- Vax
- Użytkownik
- Posty: 2913
- Rejestracja: 27 kwie 2010, o 22:07
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska / Warszawa
- Podziękował: 4 razy
- Pomógł: 612 razy
Liczba pierwsza p = 2q + 1 a generator grupy mod p
Załóżmy nie wprost, że \(\displaystyle{ a}\) oraz \(\displaystyle{ -a}\) nie są generatorami \(\displaystyle{ \pmod{p}}\), wówczas ich rząd musi dzielić i być mniejszy od \(\displaystyle{ \varphi(p) = 2q}\), skąd \(\displaystyle{ ord_pa = 1 \vee ord_pa = 2 \vee ord_pa = q}\), 2 pierwsze przypadki powodują sprzeczność z założeniem \(\displaystyle{ a^3-a \not\equiv 0\pmod{p}}\), więc może być jedynie \(\displaystyle{ ord_pa = q}\), analogicznie dochodzimy do tego, że \(\displaystyle{ ord_p(-a) = q}\), czyli musi być \(\displaystyle{ a^q = (-a)^q \pmod{p}}\) a stąd sprzeczność, ponieważ \(\displaystyle{ q}\) jest nieparzyste, \(\displaystyle{ p \neq 2}\) oraz \(\displaystyle{ a \not\equiv 0\pmod{p}}\).