Symbol Legendre'a i kongruencje

[exciter]

Witam

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]

[_el_doopa]

2)
symbol jacobiego jest multiplykatywny tzn:
\(\displaystyle{ ({a\over bc})=({a\over b})({a\over c})}\)
co za tym idzie:
\(\displaystyle{ ({a \over n})=({a \over p})^k({a\over q})=1}\)
bo \(\displaystyle{ a \equiv 1 od {pq}}\)
z drugiej strony z dwumianu newtona po wywalwniu liczb podzielnych przez n mamy:
\(\displaystyle{ (1+p^{k-1}q)^{(n-1)/2}\equiv 1+{(n-1)/2}*p^{k-1}q od n}\)
jak ze mamy ze \(\displaystyle{ (p,q)=1}\) mozemy osobno rozpatrywac powyzsza kongruencje
wzgledem \(\displaystyle{ q}\) oraz \(\displaystyle{ p^k}\)
\(\displaystyle{ 1+{(n-1)/2}*p^{k-1}q\equiv 1 od q}\)
zalozmy teraz dla dowodu niewprost ze teza jest spelniona musi byc ztem z chinskiego o resztach:
\(\displaystyle{ 1+{(n-1)/2}*p^{k-1}q\equiv 1 od {p^k}}\)
\(\displaystyle{ {(n-1)}q/2\equiv 0 od p}\)
\(\displaystyle{ n-1=0 od p}\)
\(\displaystyle{ -1=0\pmod p}\)

sprzecznosc.

troche nagmatfałem ale rozwiazanie powinno byc git