Złote twierdzenie czyli ( twierdzenie) o wzajemności reszt kwadratowych

 

Na wstępie wypiszmy trochę kwadratów kolejnych liczb naturalnych:

1,       4,       9,     16,     25,     36,     49,     64,     81,   100,

121,   144,   169,   196,   225,   256,   289,   324,   361,   400,

441,   484,   529,   576,   625,   676,   729,   784,   841,   900,

951, 1024, 1089, 1156, 1225, 1296, 1369, 1444, 1521, 1600,

1681, 1764, 1849, 1036, 2025, 2116, 2209, 2304, 2401, 2500, …

Widać jasno, że końcówki liczb (ich cyfry jednostkowe) to tylko: 1, 4, 5, 6, 9, 0.

Natomiast nie pojawiają się cyfry: 2, 3, 7 i 8.

TWIERDZENIE.

Niech p i q będą dwiema różnymi, nieparzystymi liczbami pierwszymi. Wynika stąd, że p i q przystają modulo 4 albo do 1, albo do 3. W przeciwnym razie byłyby one parzyste.

Jeżeli choć jedna  z tych liczb przystaje do 1 modulo 4, to kongruencja

x2≡p (mod q)

ma rozwiązanie x wtedy i tylko wtedy, gdy kongruencja

y2≡p (mod q)

ma rozwiązanie y.

Jeżeli zaś obie liczby p i q przystają do 3 modulo 4, to kongruencja

x2≡p (mod q)

ma rozwiązanie x wtedy i tylko wtedy, gdy kongruencja

y2≡p (mod q)

nie ma rozwiązania.

 

Powyższe twierdzenie sformułował w 1783 roku wielki Euler, nie podając jednak dowodu. Pierwszy dowód podał Legendre, ale okazało się, że jest niepoprawny. Dopiero Książe matematyków Gauss opublikował poprawny dowód twierdzenia w roku 1796 i nazwał je „aureum theorema” (złotym twierdzeniem).

Powyższe twierdzenie można zapisać inaczej wykorzystując symbol Legendre’a:

(p/q)=1, jeżeli p jest resztą kwadratową modulo q, zaś równa się -1 w przeciwnym wypadku.

Wtedy twierdzenie dają się zapisać następująco:

(p/q)(q/p)=(-1) (p-1)(q-1)/4.

Rzeczywiście (p-1)(q-1)/4 jest parzyste, gdy przynajmniej jedna z liczb p lub q przystaje do 1 modulo 4, zaś nieparzyste, gdy obie te liczby przystają do 3 modulo 4.

Zanim przejdziemy do przykładów warto wypisać kilka własności symbolu Legendre’a.

Funkcję tę można obliczyć ze wzoru

(a/p)≡a(p-1)/2 mod p, gdzie wartości tej funkcji (a/p) ∈{-1, 0, 1}.

Jeśli a≡b mod p, to (a/p)=(b/p)

(1/p)≡1(p-1)/2 mod p =1

(-1/p)≡(-1) (p-1)/2 mod p= 1, jeżeli p≡1 mod 4.

(-1/p)≡(-1) (p-1)/2 mod p= -1, jeżeli p≡3 mod 4.

(2/p)≡2(p-1)/2 mod p =(-1) (p-1)(p+1)/8

(a/p)(b/p)=(ab/p)

 

Przykłady:

1) Niech p=3 q=5, czyli obie liczby są postaci 4k+3 i 4k+1. Wtedy nie istnieje x takie, że

x2≡3 (mod 5), gdyż żaden kwadrat nie kończy się na 3, ani na 8. Zatem i nie istnieje y

takie, że y2≡5 (mod 3).

2) Niech p=3 q=7, czyli obie liczby są postaci 4k+3. Wtedy nie istnieje x takie, że

x2≡3 (mod 7), bo istnieje wiele wartości y takich, że y2≡7 (mod 3), np.:   y=4, y=5, y=7, y=8, y=10, … Właściwie są to wszystkie liczby z wyjątkiem liczb postaci y=3k.

3) Niech p=3 q=11, czyli obie liczby są postaci 4k+3. Wtedy istnieje x  takie, że

x2≡3 (mod 11), bo  62≡3 (mod 11). Zatem nie istnieje y takie, że   y2≡11 (mod 3).

4) Niech p=5 q=13, czyli obie liczby są postaci 4k+1. Wtedy nie istnieją x i y takie,  że

x2≡5 (mod 13)  i  y2≡13 (mod 5), bo y2≡13 (mod 5)≡3 (mod 5), a żaden z kwadratów liczb naturalnych nie kończy się na 3 lub 8.

5) Niech p=5 q=29, czyli obie liczby są postaci 4k+1. Wtedy istnieją x i y takie, że

x2≡5 (mod 29)  i  y2≡29 (mod 5)≡4 (mod 5),  np. y=2,3,5,7,8,12,13,15,17,18, mamy zatem  gwarancję, że istnieje odpowiednie x. I rzeczywiście dla x=11 mamy

112=121=29∙4+5=116+5, zaś dla x=18 mamy 182-5=324-5=319=29∙11.

Widać że jest to dość potężne narzędzie np. dla p=11, q=467=42×11+5 nie istnieje x takie, że

x2≡11 (mod 467), bo dla y=4 mamy y2≡467 (mod 11)≡ 5 (mod 11)≡16.

 

Widać że jest to dość potężne narzędzie np. dla p=13, q=467=13×35+12 istnieje x takie, że

x2≡13 (mod 467), bo dla y=5 mamy y2≡467 (mod 13)≡

≡12 (mod 13)≡25.

I rzeczywiście dla x=78 mamy 782=6084=13∙467+13

 

Widać że jest to dość potężne narzędzie np. dla p=13, q=3571=13×274+9 twierdzenie o wzajemności reszt kwadratowych gwarantuje istnienie x takiego, że

x2≡13 (mod 3571), bo dla y=3 mamy y2≡3571 (mod 13)≡ 9 (mod 13)≡9 (rozwiązania dają też wartości y=10, y=16, y=23, itd.)

I rzeczywiście dla x=786 mamy 7862=617796=173∙3571+13. Nie mniej znalezienie tak dużego x trudno dokonać bez wsparcia komputera, a i być może, szukanie go bez gwarancji, którą daje nam twierdzenie, nie byłoby tak owocne.

(Nie mogę tutaj powstrzymać się od skojarzeń związanych z mechaniką kwantową i tak zagadkowym zjawiskiem jak splątanie kwantowe!)