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:
