Wykaż, że kongruencja kwadratowa

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
max123321
Użytkownik
Użytkownik
Posty: 3388
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 975 razy
Pomógł: 3 razy

Wykaż, że kongruencja kwadratowa

Post autor: max123321 »

Wykaż, że kongruencja kwadratowa z modułem \(\displaystyle{ p>2}\) ma dokładnie \(\displaystyle{ \frac{p-1}{2}}\) reszt kwadratowych i tylko samo niereszt kwadratowych.

Jak to zrobić?
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Wykaż, że kongruencja kwadratowa

Post autor: arek1357 »

Zauważ, że jeżeli kongurencja:

\(\displaystyle{ x^2=a}\) oczywiście modulo \(\displaystyle{ p}\)

ma albo ze rozwiązań, albo ma dwa rozwiązania:

\(\displaystyle{ x,y}\)

\(\displaystyle{ x^2=y^2}\)

z tego:

\(\displaystyle{ p|x^2-y^2=(x-y)(x+y) \Rightarrow p|x+y \vee p|x-y}\)

a stąd:

\(\displaystyle{ x= \pm y}\)

Czyli wynika stąd,że jeżeli kongurencja ma dwa rozwiązania są to rozwiązania różniące się znakiem...

a to, że ma : \(\displaystyle{ \frac{p-1}{2}}\) - reszt i tyle samo niereszt kwadratowych wynika z faktu:

\(\displaystyle{ x^2=1, x^2=2, x^2=3,...,x^2=p-1}\)

Każda z tych kongurencji albo ma dwa rozwiązania albo nie ma wcale...

Są to liczby:

\(\displaystyle{ 1^2, 2^2, 3^2,..., \left( \frac{p-1}{2}\right)^2}\)

cnd...
ODPOWIEDZ