Rozwiązywanie kongruencji typu
a

n

x

n

+ a

n-1

x

n-1

+ …. + a

1

x + a

0

≡ 0(mod m) n ∈ IN

Każdą liczbe całkowitą C taką że f(c) ≡ O (mod m) nazywamy pierwiastkiem kongruencji

Spostrzeżenie 1.

Niech C będzie pierwiastkiem kongruencji f(x) ≡ c (mod m). Jeśli d ≡ c (mod m) to d jest również
pierwiastkiem tej kongruencji

Dowód Skoro C jest pierwiastkiem naszej kongruencji to f(c) ≡ 0(mod m). Skoro d ≡ c (mod m) to nna mocy
twierdzenia f(d) ≡ f(c)(mod m)
Ponieważ f(d) ≡ f(c)(mod m) i f(c) ≡ 0(mod m). Z def pierwiastka kongruencji wynika, że d jest pierwiastkiem
kongruencji f(x) ≡ 0 (mod m)

Spostrzeżenie 2

.

Wszystkie pierwiastki kongruencji

możemy wyznaczyć sprawdzając jej prawdziwość dla liczb {0,1,2,…n-1} czyli dla wszystkich reszt mod m.

Dowód Załóżmy że liczba całkowita c jest pierwiastkiem naszej kongruencji, czyli f(c) ≡ 0 (mod m)
Niech

d = c + km

k∈Z

Wówczas

f(d) ≡ 0 ( mod m)

Jeśli zatem sprawdzimy prawdziwość kongruencji f(x) = 0(mod m) dla liczb {0,1,2,…n-1} to tym samym
sprawdzimy prawdziwość tej kongruencji dla wszystkich liczb całkowitych.

Przyjęto nie rozróżniać pierwiastków kongruencji takich które przystają do siebie modulo m.
Traktujemy takie pierwiastki jako jeden pierwiastek kongruencji f(d) ≡ 0 ( mod m)
Przykład – wypisz reszty mod m

Rozwiązać kongruencje:

c)

Twierdzenie Lagrange’a (?)

Niech f(x) = a

n

x

n

+ a

n-1

x

n-1

+ …. + a

1

x + a

0

, gdzie a

0

,a

1

… ∈ Z

Jeśli p jest liczbą pierwszą taką że a

n

≡ 0 (mod p) czyli p ∤ an, to kongruencja f(x)

≡ 0 (mod p) ma co najwyżej n

pierwiastków.

Twierdzenie Wilsona

Jeśli p jest liczbą pierwszą to (p-1)! ≡ (-1)(mod p)

Twierdzenie Eulera

Dla dowolnej liczby całkowitej a względnie pierwszej

to

gdzie φ to funkcja Eulera

Twierdzenie Fermata (małe)

Wersja 1.
Dla każdej liczby całkowitej a niepodzielnej przez liczbę pierwszą p:

Wersja 2.

Dla każdej a ∈ Z zachodzi

gdzie

Algebra abstrakcyjna

Iloczyn kartezjański

– Iloczynem kartezjańskim zbiorów (niepustych) A i B nazywamy zbiór

Przykład