Rozdział Elementy teorii złożoności



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

Dowód


  1. n|aa, tzn. n|0,

  2. n|abn|–(ab)  n|ba,

  3. n|abn|bcn|(ab) + (bc)  n|ac.



Twierdzenie 2.3

Kongruencja jest zgodna z działaniami dodawania (+) i mnożenia (), tzn. jeżeli ab mod n oraz cd mod n, to:



  1. a + cb + d mod n,

  2. acbd mod n.
    1. Dowód


  1. n|abn|cdn|ab + cd n|(a + c) – (b + d),

  2. n|abn|cdn|(ab)cn|(cd)bn|(ab)c + (cd)bn|acbd.


Załóżmy, że ab mod n. Wtedy dla dowolnego mN zachodzi ambm mod n (co wynika z twierdzenia 2.3). Natomiast nie jest prawdą, że cacb mod n dla dowolnego cZ.

Oznaczmy Zn = {0, 1, 2, ..., n – 1}. Zbiór Zn jest zbiorem wszystkich reszt z dzielenia przez n.
Twierdzenie 2.4

Dla aZn istnieje taki element a1Zn, że aa1  1 mod n  (a, n) = 1.

Wtedy a1 jest elementem odwrotnym do elementu a w zbiorze Zn.

    1. Dowód


„”

Niech a1Zn jest elementem odwrotnym do aZn czyli aa1  1 mod n.

Załóżmy przeciwnie, że (a, n) = d > 1, stąd istnieje taka liczba całkowita k, że aa1 = d + kn. Sprzeczność z warunkiem aa1  1 mod n.

„”


Jeżeli (a, n) = 1, to za pomocą rozszerzonego algorytmu Euklidesa można wyznaczyć dwie liczby całkowite u i v takie, że ua + vn = 1, stąd n|ua – 1.

Z definicji 2.3 wynika, że ua  1 mod n, więc a1 = u.


Zbiór Zn z działaniem dodawania i mnożenia modulo n jest pierścieniem przemiennym. Oznaczmy przez Zp zbiór {0, 1, ..., p – 1}, gdzie p jest liczbą pierwszą. Zp z działaniem dodawania i mnożenia modulo p jest ciałem.
Niech Zn* będzie zbiorem elementów odwracalnych w Zn (czyli zbiorem liczb należących do Zn i względnie pierwszych z n). Wtedy zbiór Zn* z działaniem mnożenia modulo n tworzy przemienną grupę multiplikatywną.
Definicja 2.4

Niech G będzie grupą. Rzędem grupy G nazywamy ilość jej elementów i oznaczamy przez |G|.


Oczywiście |Zn*| = (n).
Twierdzenie 2. 5 (małe twierdzenie Fermata)

Niech G będzie grupą przemienną, wtedy aG a|G| = 1.



    1. Dowód


Niech g = |G| i G = {a1, a2, ..., ag}.

Najpierw należy udowodnić, że mnożenie przez element grupy jest permutacją czyli {aa1, aa2, ..., aag} = G dla dowolnego aG. Załóżmy nie wprost, że aiaj i aai = aaj. Wtedy a1aai = a1aajai = aj, co jest sprzeczne z założeniem.



Stąd = = ag, więc ag = 1.


Wniosek (twierdzenie Eulera)

Dla każdego xZn* zachodzi x(n)  1 mod n.
Z małego twierdzenia Fermata wynika następująca własność liczb pierwszych: jeżeli p jest liczbą pierwszą, to 0<x<p xp–1  1 mod p.


Twierdzenie 2.6 (chińskie twierdzenie o resztach)

Niech n  2, nN, następnie liczby q1, q2, ..., qnN będą parami względnie pierwsze oraz a1, a2, ..., anZ będą dowolne. Wtedy istnieje dokładnie jedna liczba naturalna xq1q2...qn taka, że:  1 i n xai mod qi.





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


©operacji.org 2017
wyślij wiadomość

    Strona główna