276062001

10 Podstawy teorii liczb

przeprowadzanie wielu operacji matematycznych.

Definicja 1.5.1 (relacja przystawania modulo). Niech ra E N. Mówimy, że liczby całkowite k, l przystają modulo ra, gdy m\(k — l).

Oznaczenie: k = Z(mod ra).

Liczbę ra nazywa się modułem kongruencji.

Uwaga 1.5.2. Relacja przystawania modulo m jest relacją równoważności w zbiorze liczb całkowitych.

Klasę równoważności liczby k E Z w relacji modulo ra oznaczamy [/c]_m zaś zbiór wszystkich klas równoważności w relacji modulo ra oznaczamy Z_m.

Często zapisujemy po prostu Z_m — {0,... , ra — 1} mając na myśli za każdym razem klasę równoważności reprezentowaną przez daną liczbę, (na podstawie algorytmu dzielenia z resztą wiemy, że liczby 0,... ,ra — 1 wyczerpują wszystkie klasy równoważności).

Pierwsza bardzo istotna dla dalszego ciągu uwaga, to fakt, że relacja przystawania modulo, jak łatwo sprawdzić jest zgodna z działaniami dodawania i mnożenia, co pozwoli dalej określić poprawnie takie właśnie działania na zbiorze Z_m. Konkretnie mówią nam o tym własności 1.5.3

Własność 1.5.3 (podstawowe własności kongruencji). Z: n E N, k,l,k',l' E Z takie, że k = k'(mod n) i l = l'(mod n).

T: (1) k±l = fc' ± l'(mod ri),

(2) kl = k'l'{mod n).

Dowód. Ćwiczenie.    □

Kolejny zestaw podstawowych własności kongruencji będziemy wykorzystywać dalej m.in. w rozwiązywaniu układów równań kongruencyjnych. Własności te łatwo wynikają z zastosowania zasadniczego twierdzenia arytmetyki 1.4.5 lub np. tożsamości Bezouta. 1.2.4

Własność 1.5.4 (własności kongruencji). (1) Jeśli k, l € Z, m € Z* takie, że m\kl orazm i k są względnie pierwsze, to m\l. (lemat Gaussa)

(2)    Jeśli a, m 6 N, k,l E Z to ak = al(mod am) k = l(mod m),

(3)    Jeśli m E N, a, k, l E Z takie, że NWD{a,m) — 1, to ak = al{mod m) <=> k = l(mod m).

(4)    Jeśli ai,..., a_r E Z, k E Z względnie pierwsza z a, dla i = 1,..., r, to k jest względnie pierwsza z iloczynem ai •... • a_r.

(5)    Jeśli rai,..., ra_r E Z* - parami względnie pierwsze, k € Z taka, że m,\k dla każdego i = 1,... ,r, to rai •... • m_r\k.

□

Dowód. Ćwiczenie.