Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.1.Podstawowewłasności
39
WNIOSEK4.JeżeliNi|N2,todlaN2/NiróżnychresztxmodN2resztaxmodNiprzyj-
mujezadanąwartość.
Dowód:Wynikatozpoprzedniegownioskuiuwagi,żejądrohomomorfizmuψN
1,N2
(tj.zbiórelementówprzechodzącychnazero)madokładnie
|Z/N2Z|:|Z/NiZ|lN2/Ni
elementów.
WNIOSEK5.JeśliNlNiN2,(Ni,N2)l1,xprzebiegawszystkieresztymodNi,ay
przebiegawszystkieresztymodN2,toyNi+xN2przebiegawszystkieresztymodN.
Dowód:Wystarczypokazać,żewszystkieresztyyNi+xN2modNsąróżne.Jeśli
yNi+xN2iyiNi+xiN2(modN),
tonakładającnatęrównośćodwzorowaniaψN
1,NiψN
2,N,otrzymamy
xN2ixiN2(modNi)
oraz
yNiiyiNi(modN2)
iwystarczyzastosowaćtwierdzenie2.1(iii).
2.Zajmiemysięterazrozwiązaniamikongruencjipostaci
F(x)i0(modN),
(2.2)
gdzieF(X)jestwielomianemocałkowitychwspółczynnikach.Kongruencjatakajest
równoważnarównaniu
G(x)l0
(2.3)
rozpatrywanemuwpierścieniuZ/NZ,przyczymG(X)jestwielomianemowspół-
czynnikachztegopierścienia,którepowstajeprzezzastąpienieodpowiednichwspół-
czynnikówwielomianuF(X)ichresztamizdzieleniaprzezN.Zauważmy,żestopień
wielomianuG(X)nieprzekraczastopniaF(X),alemożebyćodniegomniejszy,oczym
świadczyprzykładwielomianuF(X)l2X2lX+1przyNl2.
Liczbąrozwiązańkongruencji(2.2)nazywamyliczbęrozwiązańrównania(2.3),to
znaczydwarozwiązaniaprzystającedosiebiemodNbędziemyuważalizajedno
rozwiązanie.LiczbętębędziemyoznaczaliprzezAF(N).
NietrudnowyznaczyćAF(N)wprzypadku,gdyFjestwielomianemliniowym.
TWIERDZENIE2.2.Kongruencja
ax+bi0(modN)
(2.4)
marozwiązaniewtedyitylkowtedy,gdy(a,N)dzielib.Jeśliwarunektenjestspełniony,
tokongruencjatama(a,N)rozwiązań,awszystkieoneprzystajądosiebiewzględem
modułuN/(a,N).
Dowód:Kongruencja(2.4)jestspełnionadokładniewtedy,gdyistniejeliczbacał-
kowitaytaka,że
ax+blNy,
