cap1_c

CAPITOLUL 1

BAZELE MATEMATICE ALE SISTEMELOR DE SECRETIZARE

1.1 Noţiuni de teoria numerelor

1.1.1 Numere prime Fiind date două numere naturale m şi n, spunem că m divide pe n, sau că n

este multiplu al lui m, dacă există un număr natural k astfel încât: n m k= ⋅ . În acest caz se scrie m/n sau m:n. Relaţia de divizibilitate pe ! o vom nota cu | .

Pentru un număr n ∈ ! , un număr m ∈ ! se numeşte divizor al lui n dacă m/n. Deoarece 1n n= ⋅ şi 1n n= ⋅ , avem 1/n şi n/n, deci 1şi n sunt divizori ai lui n pentru n∀ ∈ ! . Numerele 1 şi n se numesc divizori improprii ai lui n, iar orice alt divizor al lui n se va numi divizor propriu. Orice număr natural m este divizor al lui 0, deci 0 0m= ⋅ şi m/0.

Cu excepţia numărului 1 care are un singur divizor, orice număr natural n >1 are cel puţin doi divizori distincţi, aceştia fiind 1 şi n. Un număr natural n >1 care are numai doi divizori se numeşte număr prim.

Proprietăţi 1) Relaţia de divizibilitate este o relaţie de ordine pe ! . 2) Pentru n∀ ∈ ! avem n/n deci relaţia este reflexivă. 3) Dacă m şi n sunt două numere naturale şi avem m/n şi n/m, putem scrie:

1 2 1 2şi , unde ,n k m m k n k k= = ∈ !

deci ( ) ( )1 2 1 2 1 2n k k n k k n n k k= = = , ceea ce arată că 0n = sau 1 2 1k k = Dacă 0n = , atunci 2 0m k n n= = = . Dacă 1 2 1k k = , atunci se demonstrează

că 1 2 1k k= = , deci m n= . Putem spune că relaţia este antisimetrică. 4) Dacă m, n si p sunt numere naturale şi avem: m/n şi n/p atunci:

1 2 1 2şin k m p k n k k m= = =

Deci m/p şi relaţia / este tranzitivă. Definiţie. Un număr natural p >1 este număr prim dacă şi numai dacă

pentru orice două numere naturale m şi n avem: 1sau 1p m n m n= ⋅ ⇒ = = .

Bazele matematice ale sistemelor de secretizare

2

Numerele prime sunt foarte importante în primul rând datorită faptului că orice număr natural nenul se scrie în mod unic ca un produs de numere prime. Acest rezultat, cunoscut sub numele de teorema fundamentală a aritmeticii, a devenit, prin generalizările care i s-au dat instrumentul de bază în multe capitole ale teoriei algebrice a numerelor şi ale algebrei abstracte. Numerele prime sunt de asemenea importante deoarece multe teoreme despre numere prime sunt uşor de formulat, dar foarte greu de demonstrat. Unele din aceste „teoreme” se dovedesc adevărate în toate cazurile accesibile calculului, prin mijloacele cunoscute până în prezent, dar aceste mijloace se dovedesc insuficiente pentru a se verifica valabilitatea generala a „teoremei” respective.

Una din primele probleme care s-a pus este dacă mulţimea numerelor prime este infinită sau nu. Răspunsul este dat de teorema lui Euclid.

Teorema: Mulţimea numerelor prime este infinită. Demonstraţia se face foarte simplu dacă, prin reducere la absurd

presupunem că mulţimea numerelor prime este finită. Fie { }1 2, ,..., nP p p p= această mulţime:

Considerăm numărul natural: 1 2... 1nN p p p= ⋅ + . Deoarece 1>! , există un număr p astfel încât /p ! . Deoarece p P∈ , rezultă 1 2/ ... np p p p şi deci

( )1 2/ ... 1np N p p p− = . Aşadar p/1, ceea ce contrazice faptul că p este număr prim.

Legat de faptul că mulţimea numerelor prime este infinită, s-a pus problema distribuţiei acestor numere. Notând cu ( )x∏ numărul numerelor prime mai mici decât x, se pune problema găsirii unei formule de calcul pentru

( )x∏ . Mai mulţi matematicieni au găsit experimental că: ( )x∏ ≅ln

xx

, însă

abia la sfârşitului secolului trecut J. Hadammar şi Ch. J. de la Valle Paussin au demonstrat că:

limx→∞

( )

ln

xxx

∏ =1

S-a pus şi problema dacă anumite mulţimi de numere prime, cu anumite proprietari sunt infinite sau nu. Astfel, numerele prime de forma 22 1

n+ se

numesc numere prime Fermat iar numerele prime de forma 2 1p − , unde p este număr prim, se numesc numere prime Mersenne. Nu se cunoaşte dacă mulţimea numerelor prime Fermat sau Mersenne este finită sau nu.

Teoremă. Dacă a şi n sunt numere naturale, a≥1 şi n≥2 astfel încât 1na − este număr prim, atunci 2a = şi n este număr prim.

Într-adevăr


3

( )( )1 21 1 1n n na a a a a− −− = − + + + +"

şi în ipoteza ca 1na − este prim, rezultă că a – 1=1 deci 2a = . Dacă m/n, deci n m k= ⋅ avem:

( ) ( ) ( )12 1 2 1 2 1 2 1 2 ... 2 1k m kn mk m mm − − = − = − = − + + + .

Rezultă că: 2 1 2mk m− = sau mk = m, deci m = n sau k = 1. Deci n este număr prim.

Se demonstrează că nu numai n este prim dacă şi numai dacă:

1

1 2m n

n nm m≤ ≤

− − = ∑ unde [ ]x = partea întreagă a lui x.

Se întâlnesc două situaţii: a) m/n, deci n = km si atunci

1 1 1km km k km m

− − = − + = ;

b) m nu divide pe n, deci n = km + s; 1≤ s≤m

1 0km s km s k km m+ + − − = − =

.

Deci dacă n este un număr prim, atunci el are doar cei doi divizori improprii, iar daca n are ( )nτ divizori atunci:

1

1 ( )m n

n n nm m≤ ≤

− − = τ ∑

1.2 CONGRUENŢE

1.2.1 Noţiunea de congruenţe Definiţie. Fie n un număr întreg pozitiv. Pe inelul Z al numerelor întregi,

definim o relaţie liniară, numită congruenţa modulo n. Dacă ,a b ∈ # spunem că a este congruent cu b modulo n şi scriem a ≡b (mod n), dacă n/(a – b).

Relaţia de congruenţă este o relaţie de echivalenţă. Într-adevăr: 1) Dacă a ∈ # atunci n/(a–a) deci a≡a (mod n). Deci relaţia este

reflexivă. 2) Fie ,a b ∈ # , astfel încât ,a b ∈ # . Atunci n/(a–b) şi deci n/-(a–b) sau

n/(b–a), adică b≡a (mod n). Aşadar relaţia este simetrică.


4

3) Fie , ,a b c ∈ # astfel încât a≡b (mod n) şi b≡c (mod n). Atunci n/(a–b) şi n/(b–c) deci n/((a–b) + (b–c)) sau n/(a–c) de unde rezultă a≡c (mod n). Deci relaţia este tranzitivă.

Pentru a ∈ # notăm cu: ( ){ }/ modd b a b n= ∈ ≡# clasa de echivalenţă a lui a, numită clasa de resturi modulo n. Mulţimea claselor de resturi modulo n o vom nota nZ :

( ){ }0,1,..., 1nZ n= −$ $

Pe mulţimea claselor de resturi modulo n se definesc operaţiile algebrice de adunare şi înmulţire a claselor de resturi modulo n în modul următor:

$

$ $, , .n

a b a b

a b ab a b Z

+ = +

⋅ = ∀ ∈

$

$ $

Mulţimea înzestrata cu operaţiile de adunare şi înmulţire a claselor de resturi formează un inel unitar şi comutativ. Aceasta se verifică simplu prin proprietăţile:

1. $( ) $ ( )a b c a b c+ + = + +$ $ $ $ ;

2. $ $a b b a+ = +$ $ ; 3. $ $0 0a a+ = +$ $ ; 4. $ $( ) $( ) $ 0a a a a+ − = − + =$ ;

5. $( ) $ ( )a b c a b c⋅ ⋅ = ⋅ ⋅$ $ $ $ ;

6. $ ( ) $ $

( ) $ $ $

;

;

a b c a b a c

b c a b a c a

⋅ + = ⋅ + ⋅

+ = ⋅ + ⋅

$ $ $ $

$ $ $ $

7. $ $ $ $1 1 , , , na a a a b c⋅ = ⋅ = ∀ ∈$ $ $ $ # . O clasă de resturi este ireversibilă în inelul n# dacă şi numai dacă

(a, n) = 1 (cel mai mare divizor comun). Ne propunem să descriem subnivelele şi idealele inelului n# . Orice ideal

şi orice subinel al lui n# este în particular un subgrup al grupului aditiv ( n# ,+)

al nivelului. Grupul ( n# ,+) este ciclic, fiind generat de exemplu de elementul ^1 .

Atunci orice subgrup al sau este de asemenea ciclic şi deci este de forma: $ ${ } $/ , unde nd da a d= ∈ ∈# # .


5

Un astfel de subgrup este în acelaşi timp şi subnivel şi ideal al inelului n# . Deci subinelele şi idealele lui n# coincid cu subgrupurile grupului ( n# ,+)

al inelului. De exemplu să determinam idealele inelului 6# :

$ ${ }6 0,1,2,3,4,5= $ $ $ $# .

Cum doar 1$ şi 5$ sunt inversabile în 6# rezultă că 1 5=$ $ . Considerând

celelalte elemente din 6# obţinem:

{ }$ $ $ ${ }

{ }

0 0 ;

2 4 0,2,4 ;

3 0,3 .

=

= =

=

$ $

$

$ $ $

Deci 6# are patru ideale care sunt în acelaşi timp şi subinelele sale:

{ } { } $ ${ } 60 , 0,3 , 0,2,4$ $ $ $ # .

Mulţimea n# are n elemente. În general numerele întregi a1, a2,...,an formează un sistem complet de resturi modulo n dacă:

$ $ ${ }1 2, ,..., nn a a a=# .

De exemplu mulţimea: {0,1,2,3,4,5} formează un sistem complet de resturi pentru 6# , dar şi {– 6,7,14,9,16,–1} formează tot un sistem de resturi modulo 6.

Mulţimea claselor de resturi care sunt relativ prime cu modulul formează sistemul redus de resturi împreuna cu numărul 1. În cazul 6# , {1,5} este sistem redus de resturi.

Mulţimea n# , înzestrata cu operaţiile de adunare şi înmulţire definite prin:

$

$;

,

a b a b

a b a b

+ = +

⋅ = ⋅

$

$

este un inel unitar şi comutativ, iar aplicaţia : np →# # definită prin

( ) $,p a a a= ∈ # este un morfism de inele surjectitve. Intr-adevăr :


6

( ) $ ( ) ( )( ) $ ( ) ( )

;

.

p a b a b a b p a p b

p a b a b a b p a p b

+ = + = + = +

⋅ = ⋅ = ⋅ = ⋅

$

$

1.2.2 Congruenţa ax≡b (mod m) Teoremă. Congruenţa ax≡b (mod m) are soluţii dacă şi numai dacă d, cel

mai mare divizor comun al numerelor a şi m (d = (a, m)), divide pe b. Demonstraţie. Fie $0 0,mx x∈ ∈# # o soluţie a ecuaţiei date. Atunci ( )0 modax b m≡ , deci ( )0/m ax b− , adică există 0y ∈ # astfel încât

0 0ax b my− = . Dar există d/a; d|m, rezultă ( )0 0/d ax my− , deci d/b. Reciproc, să presupunem că d|b. Se ştie că, există 0x′ şi 0y′ numere întregi, astfel încât

0 0ax my d′ ′+ = . Luând bbd

′ = ∈ # , avem ( ) ( )0 0b db a x b m y b′ ′ ′ ′ ′= = + , deci

( ) ( )0 moda x b b m′ ′ ≡ , ceea ce arată că 0 mx b′ ′ ∈ # este o soluţie a congruenţei

date. Fie ( ),d a m= şi să presupunem că d/b. Atunci dacă mmd

′ = ∈ # iar x0 este

o soluţie a congruenţei ( )modax b m≡ , avem că ( )0 0 0 0, , 2 ,..., 1x x m x m x d m′ ′ ′+ + + − sunt toate soluţii congruenţei date.

Evident că dacă (a, m)=1 atunci congruenţa ax≡b (mod m) are soluţie unică. Aceasta înseamnă că dacă m şi a sunt relativ prime, atunci există totdeauna 1a− (mod m).

Definiţie: Un element ma ∈ # este unitate în m# dacă există mb ∈ # astfel încât ab=1 (mod m).

Se poate astfel descrie grupul ( )mU # care conţine unităţile inelului m# :

( ) { }1 2, ,...,

nm i i iU a a a=# .

În acest caz numărul n se numeşte indicatorul Euler al lui m şi este egal cu numărul elementelor relativ prime cu m plus 1. Aceasta se notează ( )mϕ .

De exemplu ( ) { }12 1,5,7,11U =# , deci ( )12 4ϕ = . Teorema lui Euler. Pentru orice număr întreg a relativ prim cu m avem

( ) ( )1 modma mϕ ≡ .

Demonstraţie: Fie ( ){ }1 2, ,..., ma a aϕ un sistem redus de resturi modulo m.

Atunci şi ( )1 2, ,..., maa aa aaϕ este de asemenea un sistem redus de resturi. Produsul ( ) ( )1 2 1 2... ...m ma a a aa aa aaϕ ϕ≡ ⋅ este comutativ, deci

( )( )

( )1 2 1 2... ...mm ma a a a a a aϕ

ϕ ϕ≡ ⋅ ⋅ . De aici rezultă ( ) ( )1 modulo ma mϕ ≡ .


7

Daca m = p, p fiind un număr prim, atunci orice număr a cu p/a avem (a, p) = 1 si prin urmare congruenţa ( )modax b m≡ are soluţie unică pentru orice b ∈ # . În acest caz ( ) { }0p pU = −# # este corp.

Este evident că în cazul p este număr prim, ( ) 1p pϕ = − . O consecinţă imediată a teoremei lui Euler o constituie teorema lui

Fermat. Pentru orice p număr prim şi a ∈ # astfel încât p/a, avem

( )1 1 modpa p− ≡ . Indicatorul Euler al unui număr întreg m este o funcţie numerică

multiplicativă. Deci dacă 1 2m m m= ⋅ , atunci ( ) ( ) ( )1 2m m mϕ = ϕ ⋅ϕ . Dacă m pα= , p fiind număr prim, atunci în şirul 1,2,..., ,...,p pα sunt

1p pα α−− termeni relativ primi cu pα . Deci ( ) 1p p pα α α−ϕ = − .

Pe această bază se poate calcula indicatorul Euler când 1 21 2 ... k

km p p pαα α= ⋅ .

( )1 2

1 1 11 1 ... 1k

m mp p p

ϕ = − ⋅ − −

.

De exemplu, fie 3120 2 3 5m = = ⋅ ⋅

( ) 1 1 1 1 2 4120 120 1 1 1 120 322 3 5 2 3 5

ϕ = − ⋅ − ⋅ − = ⋅ ⋅ ⋅ = .

Se demonstrează că ( )/d n

d nϕ =∑ .

De exemplu, pentru n = 12, avem

( ) ( ) ( ) ( ) ( ) ( ) ( )/

1 2 3 4 6 12

1 1 2 2 2 4 12.d n

dϕ = ϕ + ϕ + ϕ + ϕ + ϕ + ϕ =

= + + + + + =

∑

Dacă notăm cu ( )nτ numărul divizorilor lui n (inclusiv divizorii

improprii) şi n este dat de relaţia: 1 21 2 ... k

kn p p pαα α= ⋅ , atunci ( )nτ se determină cu ajutorul relaţiei ( ) ( ) ( ) ( )1 21 1 ... 1knτ = α + ⋅ α + α + şi este egal cu numărul termenilor produsului.

( )( ) ( )1 22 2 21 1 2 21 21 ... 1 ... ... 1 ... .k

k k kP p p p p p p p p pαα α= + + + + + + + + + + + +


8

Teorema chineză a resturilor Fie 1 2, ,..., sm m m numere întregi cu ( ), 1i jm m = pentru orice

{ }, 1,2,...,i j s∈ , i j≠ şi 1 2, ,..., sb b b numere întregi oarecare. Atunci există un număr întreg x, soluţie a sistemului de congruenţe:

( )( )

( )

1 1

2 2

mod

mod..........................

mods s

x b m

x b m

x b m

≡

≡

≡

si, pentru orice altă soluţie y a aceluiaşi sistem avem ( )modx y m≡ , unde

1 2... sm m m m= ⋅ .

Demonstratie: Pentru fiecare { }1,2,...,i s∈ notăm ii

mnm

= , cu ( ), 1i in m = .

Există numerele întregi ,i iu ν astfel încât 1i i i iu m n+ ν = . Luăm i i ie n= ν şi

atunci este evident că ( )1 modi ie m= şi ( )0 mod ,i je m i j≡ ≠ . Luând 1

s

i ii

x b e=

≡∑

avem ( )modi i jx b e m≡ , deci ( )modi ix b m≡ ştiind că ( )1 modi ie m≡ .

Exemplu:

( )( )( )

1 mod7 ;

4 mod9 ;

3 mod5 ;

x

x

x

≡

≡

≡

Avem:

1 1

2 2

3 3

7; 1;9; 4;5; 3.

m bm bm b

= == == =

Deci


9

1 2 3

11

22

33

315;

45;

35;

63.

m m m mmnmmnmmnm

= ⋅ ⋅ =

= =

= =

= =

Soluţia generală a sistemului de congruenţe va fi ( )3

1

modi i ii

x b n m=

≡ ν∑ .

Se calculează ( ), 1,2,3i iν = , astfel:

( )1 modi i in m⋅ ν ≡ .

Deci

( )( ) ( ) ( )( ) ( )( ) ( )( ) ( ) ( )

( ) ( )( ) ( )

( )( ) ( ) ( )

( )( ) ( )

1 1 1

1

7 11

51

2 2 2

25

2

2

3 3

33

3

1 mod ;

3 1 mod7 ; 45 mod7 3 mod7 ;

3 ; 7 6;

3 mod7 5 mod7 ;

1 mod ; 35 mod9 8 mod9 ;

8 1 mod9 ; 9 6;

8 mod9 8 8 8 8 mod9 ;

8 mod9 ;

1 mod5 ; 63 mod5 3 mod5 ;

3 1 mod5 ;

3 mod5 2 mod5 ;

1 5 45 4 8 3

n m

n m

n

x

ϕ −

ν ≡

ν ≡ =

ν ≡ ϕ =

ν ≡ =

ν ≡ =

ν ≡ ϕ =

ν ≡ = ⋅ ⋅ ⋅

ν ≡

ν ≡ =

ν ≡

ν ≡ =

= ⋅ ⋅ + ⋅ ⋅ ( )5 3 2 63 148 mod315 .+ ⋅ ⋅ =

1.2.3 Congruenţa de gradul al II-lea Fie congruenţa: ( )2 0 mod , 0ay by c s a+ + ≡ ≠ . Prin prelucrări succesive, această congruenţă poate fi adusă la forma ( )2 modx n m≡ :


10

( )( )

( ) ( )

2

2 2

2 2

0 mod / 4

4 4 4 0 mod4

2 4 0 mod4 .

ay by c s a

a y aby ac as

ay b ac b as

+ + ≡

+ + ≡

+ + − ≡

Notăm 2

2

44

ay b x

b ac nas m

+ ≡

− ≡ ≡

şi ecuaţia devine ( )2 modx n m≡ .

Numărul n +∈ # relativ prim cu m se numeşte rest pătratic modulo m, dacă congruenţa ( )2 modx n m≡ are soluţii, şi nerest pătratic în caz contrar.

În cazul m = 2, congruenţa ( )2 mod2x n≡ are totdeauna soluţii, şi anume:

1, pentru 1;0, pentru 0.

x nx n

= == =

Pentru cazul m = p număr prim, 3m ≥ , într-un sistem de resturi modulo

p există 1pp− resturi pătratice şi 1p

p− neresturi pătratice.

Stabilirea faptului că n este sau nu rest pătratic modulo p se poate face cu

ajutorul simbolului lui Legendre np

care se defineşte astfel:

1 rest pătraticmod1 nerest pătraticmodn pn

n pp = −

O serie de proprietari ale simbolurilor lui Legendre permit cu uşurinţă calculul acestora:

a) 1 21 2... ss n n nn n np p pp

= ⋅

" ;

b) 2

1 2 1n n np p

= ;

c) ( )1 112

pp

− −= −

;

d) ( )22 118

pp

−= −

;

e) ( ) 1 112 2

p p q qq p

− −= − ⋅

.


11

Simbolul lui Legendre se utilizează în cazul în care p este număr prim. O generalizare a acesteia o reprezintă simbolul lui Jacobi care este valabil şi pentru

1 2... , numere prime, 2r i im p p p p p= ⋅ = >

1 2...

r

a a a am p p p

= ⋅ .

Pentru orice ( )1 moda a m≡ avem 1a am m

= .

Simbolul lui Legendre se poate calcula şi cu ajutorul relaţiei lui Euler:

( )1

2 modpn n p

p

− ≡

.

Pentru această relaţie există şi o generalizare pentru resturi de ordin n şi anume: numărul a este rest de ordin n pentru modulul p atunci şi numai atunci când:

( ) ( )1

d 1 mod , unde d , 1p

a p n p−

≡ = −

Există în acest caz 1d

p − resturi de ordin n faţă de modulul p.

Numărul soluţiilor congruenţei: ( )2 modx n m≡ îl notăm cu ( ),N n m şi se calculează astfel:

a) cazul , 1m pα= α ≥ , p număr prim:

( )0, 1

,2, 1

np

N n pnp

α

= − =

=

b) cazul 1; ;m p n p nα β= = ⋅ α > β:

( )1, 0N p n pβ α⋅ = dacă β este impar;

( ) ( )21 1, ,N p n p p N n p

ββ α α−β⋅ = ⋅ pentru β număr par.

1.2.3 Logaritmi discreţi Fie un sistem de secretizare cu chei publice de tip exponenţial, R.S.A., în

care modulul m este făcut public, iar exponentul de criptare e este păstrat secret.


12

Presupunem că un criptanalist a interceptat cel puţin o pereche ( ), eM M şi

încearcă să spargă sistemul, adică să găsească exponentul de decriptare d. Deci criptanalistul se găseşte în faţa problemei de a găsi ( )log mode

M M m . Acesta este un caz special de calculare a logaritmilor discreţi. Tăria metodei constă tocmai în dificultatea calculării acestui logaritm. Dacă consideram ecuaţia

xa y= pentru numere reale pozitive, problema găsirii lui x cunoscând pe a şi y este aproape aceeaşi cu a găsi pe y ştiindu-i pe a şi x. Găsirea soluţiei presupune efectuarea unor calcule mai mult sau mai puţin complicate şi căutarea în tabele de logaritmi. Problema este complet diferită dacă se lucrează cu logaritmi discreţi. Noţiunea generală de logaritm discret poate fi formulată după cum urmează. Fie g un element al unui grup finit G şi fie y un alt element din G. Atunci orice număr întreg pozitiv x, astfel încât xg y= se numeşte logaritm discret al lui y în baza g. Evident, orice element y al lui G are un logaritm discret în baza g dacă şi numai dacă G este ciclic cu generatorul g. De exemplu, în grupul multiplicativ al numerelor întregi modulat numai 1,2,4 au un logaritm discret în baza doi dar toate numerele au un logaritm discret în baza trei:

( )1 2 3 4 5 636 2 1 4 5 3

xyyx =

Dacă ( )23x GF∈ , atunci cu ajutorul ecuaţiei 2 2 2 0x x+ + = se pot

genera toate elementele câmpului ( )23GF ridicând la putere un element x numit

element generator: 1 2 3 4 5 6 7 8

1 2 1 2 2 2 2 2 1i

i

α α α + α + α α + α +

şi atunci: 1 2 1 2 2 2 1 2 2

log 8 4 1 2 7 5 3 6y

yα

α α + α + α α + α +

Grupurile cu cardinalitate mică nu prezintă dificultăţi de calcul. Există şi algoritmi eficienţi de calcul al logaritmilor discreţi pentru unele cazuri speciale. În general însă, calculul logaritmilor discreţi sunt consideraţi de aceeaşi dificultate ca şi algoritmi pentru factorizarea lui m. Algoritmul propus de Silver, Pohlig şi Hellman, probabil cel mai bun algoritm general de acest tip, este exemplificat după cum urmează şi el lucrează atunci când factorii primi ai lui m sunt mici.


13

Fie ( ), nGF q q p= un câmp finit. Consideram logaritmi discreţi în baza g, unde g este generator pentru ( )GF q . Pentru fiecare divizor d prim al lui q – 1, calculăm numerele:

( ) ( )1

d,d mod , 0qi

a i g q i p−

= ≤ < .

Dacă fiecare d care îl divide pe q – 1 este mai mic atunci mărimea tabelei precalculate conţinând numerele auxiliare a (i, d) este acceptabilă, destul de uşor de realizat.

De exemplu, GF (181) şi 2q = (2 este într-adevăr un generator). Acum 2 2180 2 3 5= ⋅ ⋅ şi tabela numerelor a (i, d) arată ca mai jos:

α

i 2 3 5

0 1 1 1 1 180 48 59 2 132 42 3 125 4 135

Să calculăm acum logaritmul discret al lui 62 în baza 2. În general dacă

1 dq α− = π , atunci pentru a găsi logaritmul discret x al lui y în baza g este

suficient să găsim ( ),moddx α pentru fiecare d din factorizarea lui q – 1.

Folosind teorema chineză a resturilor x este uşor de calculat din valorile

( ),moddx α . Pentru a calcula ( ),moddx α , considerăm reprezentarea acestui

număr în baza d:

( ) 10 1 1,modd d ... d ; 0 d 1ix x x x xα α−

α+= + + + ≤ ≤ − .

În exemplul dat considerăm factorul 2d 3α = şi scriem ( ) 0 1,mod181 3z x x= + .

Pentru a afla 0x calculăm 1

d ,modq

y q−

, care este egal cu a(i, d) pentru

un număr i. Alegem 0x i= . În exemplul dat, ( )6062 ,mod181 48= , deci 0 1x = .

Acest lucru este valabil, în general, deoarece ( )1,mod 1qg q− = deci.


14

( ) ( )( )( )

01 11d d d

0,d modq x qq

y g g a x qα − −−

≡ = ≡ .

Pentru a-l obţine pe 1x , calculăm mai întâi inversul 0xg− al lui

( )0 modxg q şi considerăm 01

xy yg−= . Dacă acum ( )21

d1 ,mod ,dq

y q a i−

=

,

atunci 1x i= . Pentru a-l obţine pe 2x , considerăm numărul 0 1d2

x xy yg− −= şi

calculăm 21

d2 ,modq

y q−

.

Procedura se repetă până când este găsit ( ),moddx α .

În exemplul dat găsim 1 31y = . Aceasta implică faptul că

( )2180

20311 ,mod181 ,mod181 1y y

= =

, deci 1 0x = şi ( )1 mod9z ≡ .

Să considerăm acum factorul 2d 2α = . Trebuie să determinăm 0 12x x+ .

Deoarece ( )9062 ,mod181 1= , rezultă că 0 0x = . Acum 1 62y y= = şi

( )4562 ,mod181 1= , de unde 1 0x = şi ( )0 mod4z ≡ .

Acum considerăm 15d α = . Trebuie determinat doar 2x . Deoarece

( )3662 ,mod181 1= rezultă 0 0x = şi ( )0 mod5z ≡ .

Deci avem de rezolvat congruenţele:

( )( ) ( )( )

0 mod4

0 mod5 100 mod180

0 mod9 log62 100

z

z z

z

≡

≡ ⇒ ≡

≡ =

1.3 Inele de polinoame

1.3.1 Proprietăţi generale Fie R un inel comutativ şi unitar şi fie ( )NR mulţimea şirurilor

( )0 1, ,..., ,... ,n if a a a a R= ∈ care au numai un număr finit de termeni ia nenuli. Există deci un număr natural m astfel încât 0ia = , pentru orice i > m.


15

1) Şirurile ( )0 1, ,..., ,...nf a a a= şi ( )0 1, ,..., ,...ng b b b= sunt egale dacă şi

numai dacă: i ia b= pentru orice i. Pe mulţimea ( )NR se definesc două operaţii

algebrice, adunarea şi înmulţirea, în raport cu care ( )NR devine un inel comutativ şi unitar.

2) Dacă ( ), Nf g R∈ , atunci { }max ,k m n>

( )0 0 1 1, ,..., ,...n nf g a b a b a b+ = + + + aparţine de asemenea mulţimii ( )NR . Într-adevăr, dacă m şi n sunt două numere naturale astfel încât 0ia = pentru orice i > m şi 0jb = pentru orice j > n atunci 0k ka b+ = pentru orice

{ }max ,k m n> .

3) Se verifică uşor că ( ),NR + formează un grup abelian, elementul nul

fiind (0,0,0,...). 4) Pentru orice element ( )0 1, ,..., ,...nf a a a= opusul său va fi ( )0 1, ,..., ,...nf a a a− = − − − .

5) Înmulţirea pe ( )NR se defineşte astfel: ( )0 1, ,..., ,...kf g c c c⋅ = , unde k i j

i j kc a b

+ =

= ∑ pentru orice k = 0,1,2,...

6) Să arătăm că ( )Nf g R⋅ ∈ . Într-adevăr 0kc = pentru orice k m n> + .

7) Înmulţirea pe ( )NR este asociativă, comutativă şi are element unitatea, (1,0,0,...), proprietăţi care se verifică cu uşurinţă.

8) În plus operaţia de înmulţire este distributivă faţă de adunare, adică:

şi ( )

( )f g h fg fh

f g h fh gh

+ = +

+ = +

În concluzie, s-a demonstrat că ( )( ),NR + formează un inel unitar

comutativ. Elementele acestui inel se numesc polinoame cu coeficienţi în R. Gradul unui polinom se notează cu grad (f) şi este dat de coeficientul

dominant na al polinomului f, deci: ( )grad f n= dacă 0ia = pentru orice i > n şi 0na ≠ .

Notăm prin X polinomul (0,1,0,...) care se numeşte nedeterminata x.

Înmulţirea polinoamelor ne dă nori

0,0,...,1,0,...nX = %&'&( cu 1 aflat pe poziţia (n + 1).

Fie f un polinom de grad n ai cărui coeficienţi sunt 0 1, ,..., na a a , adică

( )0 1, ,..., nf a a a= .


16

Folosind adunarea şi înmulţirea definite pe ( )NR se obţine:

( ) ( ) ( )

( ) ( ) ( ) ( )

0 1

0 1nori

,0,0,...,0 0, ,0,...,0 ... 0,0,..., ,0

,0,0,... ,0,0,... 0,1,0,... ... ,0,0,... 0,0,...,1,0,... ,

n

n

f a a a

a a a

= + + + =

= + ⋅ + + ⋅ %&'&(

deci 20 1 2

0

...n

n in i

if a a x a x a x a x

=

= + + + + =∑ .

Mulţimea ( )NR se mai poate nota R [x] şi se numeşte inelul polinoamelor în nedeterminata X cu coeficienţi în inelul R.

Fie un inel şi f, g două polinoame din R [x], atunci: 1. ( ) ( ) ( )grad max grad ,gradf g f g+ ≤ ; 2. ( ) ( ) ( )grad grad gradfg f g≤ + . Avem egalitate dacă f şi g sunt nenule iar cel puţin unul dintre coeficienţii

dominanţi ai lui f şi g nu este divizor al lui zero. Fie R un inel comutativ şi unitar şi inelul polinoamelor R [x]. Atunci au

loc afirmaţiile: - un element a R∈ este inversabil în R dacă şi numai dacă a este

inversabil în R[x]; - dacă R este domeniu de integritate, atunci R[x] este de asemenea

domeniu de integritate şi ( ) [ ]( )U R U R x= , unde [ ]:u R R x→ este un morfism al lui R pe R[x] şi ( ) ( ),0,0,...u a a= .

Teoremă. Fie R un inel comutativ şi unitar şi R[x] inelul polinoamelor de o nedeterminată cu coeficienţi în R şi [ ]:u R R x→ morfismul canonic. Atunci oricare ar fi inelul comutativ unitar S, morfismul de inele : R Sν → şi x S∈ , există un unic morfism de inele [ ]: R x Sϕ → astfel încât ( )u x x= şi diagrama să fie comutativă.

Demonstraţie. Să definim mai întâi morfismul ϕ . Dacă [ ]f R x∈ ,

0

mi

ii

f a x=

=∑ , atunci ( ) ( )0

mi

ii

f a x=

ϕ = ν∑ .

Arătam că ϕ are proprietăţile din enunţ. Fie 0

ni

ii

g b x=

=∑ un alt polinom

din R[x] şi să presupunem că n ≥ m. Completând eventual polinomul f cu termeni ai căror coeficienţi sunt zero, putem scrie:

0

ni

ii

f a x=

=∑ ,


17

unde 1 2 ... 0m m na a a+ += = = = . Atunci

( ) ( )

( ) ( )( ) ( ) ( ) ( ) ( )

0 0 0

0 0 0

.

n n ni i i

i i i ii i i

n n ni i i

i i i ii i i

f g a x b x a b x

a b x a x b x f g

= = =

= = =

ϕ + = ϕ + = ν + =

= ν + ν = ν + ν = ϕ + ϕ

∑ ∑ ∑

∑ ∑ ∑

Dacă notăm cu kc , coeficienţii produsului fg, avem k i ji j k

c a b+ =

= ∑ , şi cum

ν este un morfism de inele obţinem ( ) ( ) ( )i i ii j k

c a b+ =

ν = ν ⋅ν∑ .

Ţinând seama de acest lucru se verifică imediat că:

( ) ( ) ( )fg f gν = ν ⋅ ν .

Comutativitatea diagramei se verifică uşor. Într-adevăr dacă a ∈ ) , avem:

( )( ) ( )( ) ( ) ( ) ( ) ( )0 0u a u a a ax a x aϕ ⋅ = ϕ = ϕ = ϕ = ν = ν .

Deci uϕ ⋅ = ν .

1.3.2 Factorialitatea inelelor de polinoame Un inel R, se numeşte inel factorial sau cu descompunere unică în factori

primi (ireductibili) dacă orice element neinversabil şi nenul din R se descompune într-un produs finit de elemente prime. Orice inel de polinoame de o nedeterminată este un inel factorial.

Teoremă. Fie R un inel factorial. Atunci inelul de polinoame R[x] este factorial. Pentru demonstraţie avem nevoie de o serie de rezultate preliminarii.

Lema 1. Fie a ∈ ) şi [ ]0 1 ... nnf a a x a x x= + + + ∈ ) . Dacă /a f , atunci

/ ia a oricare ar fi i = 0,1,...,n. Demonstraţie. Cum /a f rezultă că:

( )0 1 0 1... ...n nn nf a b b x b x ab ab x ab x= + + + = + + ,

deci / ia a . Lema 2. Fie R un domeniu de integritate. Daca p ∈ ) este un element

prim din R atunci p este un element prim în R[x]. Demonstraţie. Fie [ ],f g R x∈ astfel încât /p fg . Presupunem că

0 1 ... nnf a a x a x= + + + şi 0 1 ... m

mg b b x b x= + + + şi că /p f şi /p g . Conform lemei anterioare, rezultă că există un ka astfel încât / kp a . Analog, din /p g


18

rezultă că există lb astfel încât / lp b . Deci 0 1 1/ , / ,..., / kp a p a p a − şi 0 1 1/ , / ,..., / lp b p b p b − .

Coeficientul lui k lx + este

0 1 1 1 1 1 1 01

... ...k l i j k k k l k l k l k li j k

c a b a b a b a b a b a b a b+ + − + + − ++ = +

= = + + + + + + +∑ .

Deoarece / i ip a b cu i k≠ şi j l≠ , iar / k lp a b , rezultă că / k lp c + , deci /p fg , deci contradicţie, deci trebuie ca /p f sau /p g .

Presupunem acum că inelul R este factorial şi fie 0 1 ... nnf a a x a x= + + +

un polinom din R[x]. Vom nota cu ( )c f cel mai mare divizor comun al elementelor ( )0 1, ,..., na a a c f⋅ se numeşte conţinutul polinomului f. Dacă

( ) 1c f = , atunci polinomul f se numeşte primitiv. Se observă că ( )f c f f ′= ⋅ , unde f ′ este un polinom primitiv.

Lema lui Gauss (3). Dacă R este un inel factorial şi [ ],f g R x∈ atunci ( ) ( ) ( )c fg c f c g= ⋅ .

Demonstraţie. Cum ( )f c f f ′= ⋅ şi ( )g c g g′= ⋅ , rezultă ( ) ( ) ( )fg c f f c g g c fg f g′ ′ ′ ′= ⋅ ⋅ ⋅ = .Deci ( ) ( ) ( ) ( )c fg c f c g c f g′ ′= ⋅ ⋅ . Trebuie arătat că ( ) 1c f g′ ′ = . Presupunem că ( ) 1c f g′ ′ ≠ , deci există

p ∈ ) element prim, astfel încât ( )/p c f g′ ′ . Deci /p f g′ ′ , deci /p f ′ sau /p g′ rezultă că f ′ sau g′ nu sunt primitive, rezultă o contradicţie.

Lema 4. Fie R un inel factorial şi [ ],f g x∈ ) , unde g este un polinom primitiv. Dacă , 0a a∈ ≠) , şi /g af , atunci /g f

Demonstraţie. Avem [ ] ( ) ( ) ( ) ( ),af gh h R x ac f c g c h c h= ∈ = ⋅ = deoarece ( ) 1c g = .Cum ( )h c h h′= ⋅ , rezultă că ( )af g c h h′= ⋅ ⋅ sau

( ) ( ) ( )/ :af g a c f h a f g c f h c f g h′ ′ ′= ⋅ ⋅ ⋅ ⇒ = ⋅ ⋅ = ⋅ ⋅ , deci /g f . Lema 5. Fie R un inel factorial cu corpul de fracţii K, iar [ ],f g R x∈

două polinoame primitive. Atunci f şi g sunt asociate în R[x] dacă şi numai dacă sunt asociate în inelul K[x].

Demonstraţie. Evident că dacă f şi g sunt asociate în R[x] sunt asociate şi în K[x]. Invers, presupunem că f şi g sunt asociate în K[x]. Deci există [ ]u K x∈ ,

element inversabil, astfel încât g fu= . Cum u K∈ , atunci putem scrie aub

= cu

a ∈ ) şi b ∈ ) , 0, 0a b≠ ≠ . Deci bg = af şi /f g şi /g f , adică f şi g sunt asociate în inelul R[x].


19

Lema 6. Fie R un inel factorial cu K corpul său de fracţii şi [ ]f R x∈ un polinom primitiv cu grad ( ) 1f ≥ . Atunci f este ireductibil în R[x] dacă şi numai dacă f este ireductibil în K[x].

Demonstraţie: Presupunem că f este ireductibil în R[x] şi fie f = gh, cu [ ]g K x∈ şi [ ]h K x∈ şi ( )grad 1g ≥ , ( )grad 1h ≥ . Evident putem scrie

1ag gb

= , ,a b ∈ ) , ( ), 1a b = , şi [ ]1g R x∈ . Analog 1ch hd

= , ,c d ∈ ) , ( ), 1c d = ,

[ ]1h R x∈ . În plus, ( ) ( )1grad gradg g= şi ( ) ( )1grad gradh h= .

Deci 1 1 1 1a c acf g h g hb d bd

= ⋅ = .

( )( )

1 1 1

1 1 1

;

;

g c g g

h c h h

′= ⋅′= ⋅

( 1g′ şi 1h′ sunt polinoame primitive).

Obţinem 1 1f u g h′ ′= ⋅ ⋅ ; ( ) ( )1 1acu c g c hbd

= ⋅ - element inversabil din R.

Deci f şi 1 1g h′ ′⋅ sunt asociate în K[x]. Deci f şi 1 1g h′ ′⋅ sunt asociate şi în R[x]. Deci [ ]1 1,f g h U R′ ′= ν ⋅ ⋅ ν ∈ . Cum 1grad 1g ≥ şi 1grad 1h ≥ , aceasta implică că f nu este ireductibil în R[x] rezultă deci o contradicţie.

Invers, presupunem că f este ireductibil în R[x] şi că f = gh, [ ],g h R x∈ . Cum f este ireductibil în K[x] rezultă că g este inversabil sau h este inversabil în K[x]. Dacă g este inversabil în K[x], rezultă că g K∈ , adică g a= ∈ ) . Deci f ah= . Cum f este primitiv, rezultă că a este inversabil în R. Deci f este

ireductibil în R[x]. Teoremă: Fie R un inel factorial. Atunci inelul de polinoame R[x] este

factorial. Demonstraţie: Fie [ ]f R x∈ . Putem scrie ( ) 0f c f f= , unde 0f este un

polinom primitiv. Cum [ ]0f K x∈ , iar K[x] este un inel factorial, rezultă că

0 1 2... nf f f f= , unde [ ]1 2, ,..., nf f f K x∈ şi sunt polinoame ireductibile. Putem

scrie pentru , ii i i

i

af f gb

= ,unde ,i ia b ∈ ) şi [ ]ig R x∈ este un polinom primitiv,

deci ig este ireductibil în R[x]. Rezultă că 0f se scrie sub forma

0 1 2... naf g g gb

= , unde ,a b ∈ ) . Cum 0f este primitiv şi produsul 1 2... ng g g este

primitiv. Din lema 6 rezultă [ ]0 1 2... ,nf ug g g u U R= ∈ . Cum ( )c f este un produs finit de elemente prime în R, care sunt elemente prime şi în R[x], rezultă conform lemei 3 că f este un produs de elemente ireductibile în R[x]. Scrierea lui în produs de elemente ireductibile în R[x] este unică. Să presupunem că


20

1 2 1 2... ...n mf f f f g g g= = , unde [ ],i if g R x∈ sunt elemente ireductibile în R[x]. Dacă grad 1if ≥ , atunci evident ( ) 1ic f = . Deci putem scrie:

1 2 1 1 2 1... ... ... ...s s n r r mf f f f f f g g g g g+ += = ,

unde 1 2 1 2, ,..., , , ,...,s rf f f g g g ∈ ) , iar 1 1,..., , ,s n r mf f g g+ + au gradul 1≥ . Din lema lui Gauss rezultă că 1 2, ,..., sf f f şi 1 2, ,..., rg g g sunt asociate în divizibilitate în R. Cum R este factorial, rezultă că r s= şi abstracţie făcând de o renumerotare avem i if g* ∗∗∗∗ ) oricare ar fi 1 i s≤ ≤ . Rezultă: 1 1... ...s n r mf f g g+ += .

Din lema 7 rezultă m = n, şi k ng f* în K[x] oricare ar fi 1s k n+ ≤ ≤ , deci k ng f* în R[x]. Deci descompunerea este unică.

1.3.3 Criterii de ireductibilitate 1) Criteriul lui Eisenstein. Fie R un inel factorial şi K corpul funcţiilor

sale, iar 0 1 ... nnf a a x a x= + + + din R[x]. Presupunem că există un element prim

p ∈ ) cu proprietăţile: i) 0 1 1/ , / ,..., / np a p a p a − ; ii) / np a ; iii) 2

0/p a . Atunci polinomul este ireductibil în K[x]. Demonstraţie. Putem presupune că polinomul f este primitiv. prin

reducere la absurd vom presupune că f este reductibil în K[x]. Deoarece f este primitiv, rezultă că el este reductibil şi în R[x]. Fie atunci f = gh cu [ ],g h R x∈ , unde.

0 1

0 1

... , 0;

... , 0.

mm m

rr r

g b b x b x b

h c c x c x c

= + + + ≠

= + + + ≠

Prin identificare rezultă 0 0 0a b c= . Din 0/p a rezultă 0/p b sau 0/p c şi cum 2

0/p a avem că p nu divide în acelaşi timp pe 0b şi 0c . Să presupunem că 0/p b şi 0/p c . Deoarece / np a este clar că polinomul g are coeficienţi care nu

se divid cu p. Fie i minim astfel încât / ip b şi să consideram 1

01

i

i k l i j i jk l i j

a b c b c b c−

−+ = =

= = +∑ ∑ cu i m n≤ < .

∗∗∗∗ ) Relaţia * ” înseamnă asociat în divizibilitate. Dacă f g* , rezultă f/g şi g/f.


21

Deoarece 0 1/ , / ,..., /i ip b p b p b + , rezultă că 1

1

,i

j i jj

p b c i m n=

−=

≤ <∑ , şi

cum 0/ ip b c , avem evident că / ip a , contradicţie. Aplicaţie. Fie p un număr prim. Polinomul 1 ... 1pf x x−= + + + cu

coeficienţi întregi este ireductibil în Q[x]. Într-adevăr este suficient să demonstram că polinomul f (x + 1) este ireductibil în Q[x]. Avem:

( ) ( ) ( ) ( ) ( ) ( )1 2

1 1 11 1 2 1

1 1 ... 1 1 1 1 1 11

1 1 1... 1 1

...

p p p p

p p pp p p p p

p p

x x x x xf x

x xx c x c x

x C x Cx

− −

− −− − −

+ + + + + + + + − + −+ = = = =

+ −+ + + + −

= = + + +

Observăm că / ,1 1, /1kpp C k p p≤ ≤ − şi 2 1/ p

pp C − . Conform criteriului lui Eisenstein, ( )1f x + este ireductibil în Q[x] şi deci f(x) este de asemenea ireductibil în Q.

2) Criteriul de reducţie: Fie R şi S două inele factoriale, : R Sϕ → un morfism (unitar) de inele, [ ] [ ]: R x S xϕ → morfismul de inele care extinde pe

ϕ , adică dacă [ ]0 1 ... nnf a a x a x R x= + + + ∈ , atunci

( ) ( ) ( )0 ... nnf a a xϕ = ϕ + + ϕ . Presupunem că f este un polinom primitiv în R[x]

astfel încât ( ) ( )( )grad gradf f= ϕ şi ( )fϕ este ireductibil în S[x]. Atunci polinomul f este ireductibil.

Demonstraţie. Prin absurd presupunem că f este reductibil în R[x], adică f gh= cu [ ],g h R x∈ , iar g şi h nu sunt inversabile în R[x]. Cum f este primitiv,

atunci trebuie ca ( )grad 1g ≥ şi ( )grad 1h ≥ . Dar din egalitatea f = gh rezultă că ( ) ( ) ( )f g hϕ = ϕ ⋅ϕ . Cum ( )( ) ( )grad gradg gϕ ≤ şi ( )( ) ( )grad gradh hϕ ≤ iar

( )( ) ( )grad gradf fϕ = rezultă că:

( )( ) ( )( )( ) ( )

grad grad 1;

grad grad 1.

g g

h h

ϕ = ≥

ϕ = ≥

Deci ( )fϕ nu este ireductibil în S[x], contradicţie. Caz particular: Fie p un număr prim, 0 1 ... n

nf a a x a x= + + + un polinom primitiv din Z[x] şi 0 1 ... n

nf a a x a x= + + + polinomul din [ ]pZ x astfel încât ia este clasa de resturi modulo p a lui ia , pentru orice i = 0,1,...,n. Dacă

( ) ( )grad gradf f= şi f este ireductibil atunci şi f este ireductibil.


22

Aplicaţie: Polinomul 5 25 1f x x= − + are coeficienţi întregi şi este ireductibil în Z[x].

Într-adevăr, aplicăm criteriul de reducţie pentru p = 2. Avem [ ]5 2

21f x x Z x= + + ∈ , ( ) ( )grad gradf f= . Demonstrăm că f este ireductibil în

[ ]2Z x . Deoarece ( )0 1f = şi ( )1 1 0f = ≠ , rezultă că f nu are divizori de gradul întâi.

Deci ( )( )5 2 2 3 221 , , , , , , ,x x ax bx c x x x a b c+ + = + + α + β + γ + δ α β γ δ∈# .

Prin identificare rezultă:

10

01

01

ab a

a b ca b cb cc

α = α + β = γ + β + α = δ + γ + β = δ + γ =

δ =

Acest sistem nu are soluţie, deci 5 2 1x x+ + este ireductibil.

1.3.4 Polinoame ciclotomice Pentru orice număr natural 1n ≥ , rădăcinile complexe ale polinomului

( ) 1nnf x x= − se numesc rădăcini de ordin n ale unităţii. Vom nota cu nU

mulţimea acestora, adică

{ }/ 1nnU x C x= ∈ = .

Mulţimea nU conţine exact n elemente şi anume:

2 2cos sin ; 0,1,2,..., 1kk kx i k nn nπ π= + = − .

Mulţimea nU înzestrata cu operaţia de înmulţire este un „grup ciclic”, adică un grup în care toate elementele sunt puteri ale unui anumit element. Dacă

2 2cos sinin nπ πα = + , iar atunci se demonstrează că dacă 1pα = , atunci p este

multiplu de n.

Un element 2 2cos sinkk kx in nπ π= + se numeşte generator al grupului nU

(dacă prin ridicări succesive la putere se generează toate elementele mulţimii nU ) dacă şi numai dacă (k, n) = 1.


23

Grupul ciclic nU are ( )nϕ generatori care sunt rădăcinile primitive de ordinul n ale unităţii.

Pentru n numai prin mulţimea rădăcinilor primitive de ordin n este

{ }2 1, ,..., nnP −= α α α ,

unde: 2 2cos sin , 0 1k ki k n

n nπ πα = + ≤ ≤ − .

Pentru orice n N ∗∈ , polinomul

( )n

nP

f xα∈

= − α∏

se numeşte al n-lea polinom ciclotomic (al n-lea polinom de diviziune circulară). Relaţia lui Dedekind: Pentru orice 1n ≥ are loc egalitatea

/

1nd

d n

x f− =∏ ,

unde produsul se face după divizorii naturali d ai numărului n. Această relaţie, a cărei demonstraţie este relativ simplă, poate fi utilizată ca o relaţie de recurenţă cu ajutorul căreia se pot determina din aproape în aproape polinoamele ciclotonice.

De exemplu, ne propunem să calculăm polinoamele ciclotonice 1 2 3 4 5, , , ,f f f f f şi 6f .

Evident 1 1f x= − şi apoi 21 21x f f− = ⋅ . Deci 2 1f x= + 3

1 31x f f− = ⋅ , rezultă 2

3 1f x x= + + ;

41 2 41x f f f− = ⋅ ⋅ , deci ( )( )

42

41 1

1 1xf x

x x−= = +

− +;

51 51x f f− = ⋅ , deci

54 3 2

51 11

xf x x xx

−= = + + +−

;

61 2 3 61x f f f f− = ⋅ ⋅ ⋅ , deci

( )( )( )6

26 2

1 11 1 1

xf x xx x x x

−= = − +− + − +

.

Pentru n = p număr prim: 1

0

pi

pi

f x−

=

=∑ .


24

Polinomul pf este în acest caz ireductibil. Mai mult, se demonstrează (teorema lui Dedekind) că orice polinom , 1,nf n n N≥ ∈ este ireductibil în inelul Z[x] şi în inelul Q[x].

Polinoamele ciclotonice pot fi exprimate cu ajutorul funcţiei lui Möbius care este definită astfel:

( ) ( ) 1 22

1,dacă 1;

1 , ... , liber de pătrate;

0,dacă există / , număr prim.

kk

n

n n PP P n

p n p

=µ = − =

Pentru orice 1,n n N≥ ∈ avem egalitatea

( )/

1n

d dn

d nf x

µ = −∏ .

De exemplu

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )

( )( )( )( )

2 16 3 3 66

62

2 3

1 1 1 1

1 11,

1 1

f x x x x

x xx x

x x

µ µµ µ= − ⋅ − ⋅ − ⋅ − =

− −= = − +

− −

deoarece

( )( )( )( )

1 1;

2 1;

3 1;

6 1.

µ =

µ = −

µ = −

µ =

Pentru demonstrarea acestei relaţii se utilizează teorema de inversiune a lui Möbius.

Vom prezenta formulele de inversiune ale lui Möbius fără demonstraţie: a) formula aditivă

Dacă ( ) ( )/

dd n

f n g d=∑ , atunci ( ) ( )/

dd n

ng n d fd

= µ ∑ , unde

( ) ( ) 1 2

1 2

1; 1

1 ; ...

0; ... , 1

kk

j

d

d d PP P

d PP Pα

=µ = − =

= α >


25

b) formula multiplicativă

Dacă ( ) ( )/

dd n

f n g d=∑ , atunci ( ) ( )/

mn

nn m

g m f n µ = ∑ .

cap1_c

Documents