Mam problem z rozwiązaniem poniższego zadania, a właściwie kilku podpunktów w nim zawartych... arytmetyka modularna strasznie cieżko mi idzie:(
Z góry dziękuje za wszelkie podpowiedzi i wskazówki
Niech \(\displaystyle{ G(n) = \{ a : a \in Z^*_n, \ (\frac{a}{n}) \equiv a^{(n-1) / 2} \ (mod \ n) \}}\)
Wykaż, że G(n) jest podgrupą grupy \(\displaystyle{ Z^*_n}\) i wywnioskuj stąd, że \(\displaystyle{ | G(n) | \leq \frac{n-1}{2}}\)
(tutaj nie wiem jak pokazac ze dla każdego a z G(n) istnieje element odwrotny i jak udowodnic ta nierowność)
Załóżmy, że \(\displaystyle{ n = p^kq}\) gdzie p i q są liczbami nieparzystymi, p jest liczba pierwszą, \(\displaystyle{ k \geq 2}\) oraz NWD(p,q) = 1. Niech \(\displaystyle{ a \ = \ 1 \ + \ p^{k-1}q}\).
Udowodnij, że \(\displaystyle{ (\frac{a}{n}) \not \equiv a^{(n-1) / 2} \ (mod \ n)}\)
Niech \(\displaystyle{ n \ = \ p_1p_2...p_k}\), gdzie \(\displaystyle{ p_i}\) są różnymi liczbami pierwszymi. Niech \(\displaystyle{ a \ \equiv \ u \ mod \ p_1}\) oraz \(\displaystyle{ a \ \equiv \ 1 \ mod \ p_2...p_k}\),
gdzie u jest nieresztą kwadratową modulo \(\displaystyle{ p_1}\) (takie a istnieje na mocy chińskiego twierdzenia o resztach).
Wykaż, że:
\(\displaystyle{ (\frac{a}{n}) \equiv -1 \ (mod \ n)}\) lecz \(\displaystyle{ a^{(n-1) / 2} \equiv 1 \ (mod \ n)}\) a zatem \(\displaystyle{ a^{(n-1) / 2} \not \equiv 1 \ (mod \ n)}\)
Pomocne linki (mi za bardzo nie pomogły;):
i jego uogólnienie -
[url=http://pl.wikipedia.org/wiki/Reszta_kwadratowa]Reszta kwadratowa[/url]
