6161619779

Ważny wniosek wynikający z CRT:

Jeżeli gcd (n_I, n₂) = /, to para kongruencji:

x =a (mod iij) x =a (mod n₂)

ma jednoznaczne rozwiązanie: x = a (mod n/n₂)

Grupą multiplikatywną % _n jest zbiór:

9’ n = {ae 9„: gcd (a, n) = 1}.

W szczególności, gdy n jest liczbą pierwszą:

=    1 < a< n-1}.

Rzędem $' _n jest liczba elementów tego zbioru , czyli I ^ ‘ _n I. Prawdziwa jest zależność: \ $' _n\ = <j)( n ).

Twierdzenie Eulera:

n >2 Aa e ^*_n =>^a *^(n> =1 (modn)

(n jest iloczynem dwóch różnych liczb pierwszych) A rm(mod Oin)) =>a ^r =a ^s (mod n)

Wniosek: Wykładniki potęg mogą być w takim przypadku redukowane mod <p(n).