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 .