Page 36 - MATINF Nr. 8

ˆ
ˆ
36 3 REZOLVAREA ECUAT , IILOR DE FORMA F(X) = 0 IN MULT , IMEA NUMERELOR INTREGI

Caz particular, n = 3:

3
2
a 0 + a 1 X + a 2 X + a 3 X = a 0 + X(a 1 + X(a 2 + Xa 3 ))
ˆ
In acest caz se efectueaz˘a trei ˆınmult , iri.
a
Dac˘ consider˘am a 0 = 3, a 1 = 2, a 2 = 5, a 3 = 1, x = 2, atunci f(2) = 3 + 2(2 + 2(5 + 2 · 1)),
a
adic˘ f(2) = 35.
Algoritmul 1.

Date de intrare: n, a 0 , a 1 , . . . , a n , x

Date de ies , ire: f
Pasul 1. citim n, a 0 , a 1 , . . . , a n , x

Pasul 2. f = 0

Pasul 3. pentru i = n, 0, −1 execut˘a

f = a i + x ∗ f

sfˆars , it pentru

Pasul 4. afis , ˘am f

Observat ,ia 1. Algoritmul 1 calculeaz˘ valoarea f(x) folosind n + 1 ˆınmult , iri s , i n + 1 comparat , ii
a
(realizate la pasul 3), exceptˆand comparat , iile pentru citirea datelor de intrare.

3 Rezolvarea ecuatiilor de forma f(x) = 0 ˆın multimea numerelor ˆıntregi
,
,

ˆ n
In continuare vom considera f = a 0 + a 1 X + . . . + a n X un polinom de gradul n, n ≥ 1 cu
coeficient , i ˆıntregi. Pentru un polinom f de acest tip dorim un algoritm eficient de determinare
a solut , iilor ˆıntregi pentru ecuat , ia:
f(x) = 0 (1)

ˆ a
In acest scop vom utiliza urm˘atoarele rezultate din matematic˘ (pentru detalii se poate consulta
[3]):
p
Propozit , ia 1. Dac˘a ecuat , ia (1) are ca solut , ie num˘arul rat , ional , unde p s , i q sunt numere
q
ˆıntregi prime ˆıntre ele, q nenul, atunci:

a) p divide a 0

b) q divide a n

a
Propozit , ia 2. Dac˘ ecuat , ia (1) are ca solut , ie num˘arul ˆıntreg p, atunci p divide a 0 .

Folosind Propozit , ia 2 s , i Algoritmul 1 putem s˘a construim un algoritm de determinare a
solut , iilor ˆıntregi pentru ecuat , ia (1).