Rozdział Elementy teorii złożoności



Pobieranie 1,74 Mb.
Strona6/19
Data23.02.2018
Rozmiar1,74 Mb.
1   2   3   4   5   6   7   8   9   ...   19

Dowód


„Istnienie”

Niech q = q1q2...qn. Dla każdego 1  in zachodzi (­­, qi) = 1, więc istnieje taka liczba x­­i, że xi  1 mod qi. Oczywiście xi  0 mod qj dla ji.

Niech x0 = . Wtedy otrzymujemy: x0xiaiai mod qi dla każdego 1  in.

„Jedyność”

Załóżmy, że istnieją dwie liczby x0, x1q takie, że x0ai mod qi i x1ai mod qi dla 1  in.

Oczywiście x0x1 mod qi dla każdego 1  in więc x0x1 mod q1q2...qn.


          1. Pierwiastki kwadratowe modulo n


Definicja 2.5

Element aZn jest resztą kwadratową modulo n jeżeli istnieje taki element xZn, że x2a mod n. Wtedy x nazywamy pierwiastkiem kwadratowym z a modulo n.


Twierdzenie 2.7

Jeżeli n jest liczbą pierwszą, to każdy element Zn może mieć co najwyżej dwa pierwiastki kwadratowe.





1   2   3   4   5   6   7   8   9   ...   19


©operacji.org 2017
wyślij wiadomość

    Strona główna