Ilość Reszt

[mol_ksiazkowy]

Udowodnić że ilość reszt stopnia \(\displaystyle{ n}\) modulo \(\displaystyle{ p}\) to \(\displaystyle{ \frac{p-1}{(p-1, n)}}\)

Ukryta treść:    

gdzie \(\displaystyle{ (a,b)}\) to największy wspólny dzielnik liczb \(\displaystyle{ a}\) i \(\displaystyle{ b}\)
\(\displaystyle{ p}\) jest liczbą pierwszą.

[Takahashi]

Co to jest stopień reszty?

[mol_ksiazkowy]

Inaczej: Ilość takich \(\displaystyle{ r \in \{1, …, p-1 \}}\) dla których istnieje liczba naturalna \(\displaystyle{ x}\) iż \(\displaystyle{ x^n \equiv r \ (mod \ p )}\) to \(\displaystyle{ \frac{p-1}{(p-1, n)}}\)

[Kaf]

Wystarczy wykazać, że ilość pierwiastków \(\displaystyle{ n-}\)tego stopnia z jedynki w \(\displaystyle{ \ZZ / p\ZZ}\) wynosi \(\displaystyle{ (p-1,n)}\), a to wynika z tego, że grupa multiplikatywna tego ciała jest cykliczna rzędu \(\displaystyle{ p-1}\).