7/25/2019 Fisa Teorie Clase de Resturi
1/2
1
CLASEDERESTURI
CLASEDERESTURIRECAPITULARENOIUNIDEBAZ
0,1,..., 1P p estemulimearesturilormpririiunuinumrntregoarecarela p;
Pep
sedefinescdou operaii:
Adunarea: ,p este grup (comutativ), deci pentru orice element px exist opusul
p
x ,astfelnct: ( ) 0x x (calculopus: x p x );
nmulirea: ,p este monoid (comutativ) Unitile monoidului (mulimea elementelor
inversabile, notate1
px ) sunt elementele relativ prime cu :
1 1 ( ) 1p pU x x x Consecin: Dac =prim, * ,p estegrup(comutativ).
Cumsedetermin inversulunuielement p
x ?
1) Severific dac , 1x p (pentruexistena inversului 1x ) iapoidinfaptulc 1 ( ) 1x x este
echivalentcuaavea1 ( ) 1x p k ( k ),determinm 1x dndvalorilui k.
2) FolosindAlgoritmul luiEuclid (determinareac.m.m.d.c.adou numerentregi a i b ) iscrierea
(unic)ac.m.m.d.c.caocombinaieliniar dintre a ib .
ALGORITMULLUIEUCLID
Const ntro aplicare consecutiv,ntrun numrfinit depai, a Teoremeimpririi cu rest: la
fiecare nou aplicare a algoritmului,mpritorul etapei anterioare devine demprit iar restul
etapeianterioaredevinempritor.Ultimulrestnenulastfelobinut este d c.m.m.d.c ( , )a b .
Schemaalgoritmului:
Fie a ib dou numerentregi,cu a b .
1 1
1 2 2
1 2 3 3
1 1 1 1
1 2
.....................
0
n n n n n
n n n
a b c r
b r c r
r r c r
r r c r d r
r r c
STOP
Scrierea(unic)ac.m.m.d.c.caocombinaieliniar dintre a ib :
Fie ( , )a b d .Atunci ! ,x y a.. a x b y d (x i y senumesccoeficieniiluiBezout).
7/25/2019 Fisa Teorie Clase de Resturi
2/2
2
Cumsedetermin coeficieniiluiBezout?
Dup ceseaplic AlgoritmulluiEuclidisedetermin d,sescriefiecarerestdinschem dejosnsusca
diferen:1 1 1k k k k
r r r c .
Determinareainversuluiunuielement b
a : 1 moda b cuAlgoritmulluiEuclid:
Dac exist1
a
,nseamn c
, 1a b (adic
aesterelativprimcu
b,deci
1d );
Sedetermin coeficieniiluiBezout,apoisescriec.m.m.d.c.(adic 1d )cuajutorullor:
1a x b y modb
( ) mod 0 1 modax b b
1 modx a b
MICATEOREM ALUIFERMAT
Fie ,a p ,cu 0p numrprimi , 1a p .Atunci:
1 1modpa p
(sauechivalent, modpa a p )
LEMACHINEZ ARESTURILOR
Fie1 2, , ..., rm m m ntregipozitivi,relativiprimintreei( ( , ) 1i jm m , i j )i 1 2, , ..., ra a a ntregi.
Atuncisistemul:
1 1
2 2
mod
mod
.....................
modr r
a m
x a m
a m
aresoluieunic modulo1 2
...r
m m m iarformasoluieieste:
1
modr
i i i
i
a M y M
,unde ii
MM
m i 1 modi i iy M m
,1 i r .
Top Related