Redigerer Euklids algoritme (avsnitt)

==Faktorisering av polynom==

[[Polynom]] kan adderes og multipliseres sammen. De kan på den måten danne en matematisk [[ring (matematikk)|ring]] med tilsvarende egenskaper som [[heltall]]ene '''Z'''. Av den grunn kan et polynom ofte [[faktorisering|faktoriseres]] i et produkt av et eller flere andre polynom av lavere grad. Denne faktorisering kan også systematisk utføres ved hjelp av Euklids algoritme.<ref name = RA> J. Reed og J. Aarnes, ''Matematikk i vår tid'', Universitetsforlaget, Oslo (1967).</ref>

Hvis man er gitt ett polynom ''a''(''x'') og et annet ''b''(''x'') av samme eller lavere grad, kan man alltid foreta en oppsplitting av formen

: <math> a(x) = q(x)b(x) + r(x) </math>

hvor de to polynomene ''q''(''x'') og ''r''(''x'')  entydig kan bestemmes. Polynomet ''b''(''x'') kan så splittes opp på en tilsvarende måte og dermed gi opphav til et nytt restpolynom ''r''(''x'') . Denne prosessen fortsettes så til man står igjen med et restpolynom som er null. Den største felles faktor av polynomene ''a''(''x'') og ''b''(''x'') er da det foregående restpolynomet.

Fremgangsmåten kan illustreres ved et enkelt eksempel der 

: <math> a(x) = x^3 - 4x^2 - 3x + 18, \;\;\; b(x) = x^2 - 2x - 8 </math>

Da er

: <math>\begin{align} a(x) &=  (x^2 - 2x - 8)(x - 2) + x + 2\\ b(x) &= (x - 4)(x + 2) + 0 \end{align} </math> ,

slik at den felles faktor er <math> x + 2 </math>. Polynomet  ''a''(''x'') kan derfor splittes opp og man finner

: <math> x^3 - 4x^2 - 3x + 18 = (x + 2)(x - 3)^2 </math>

Det er først når de gitte polynomene har mye høyere grad, at denne algoritmen virkelig kommer til sin fulle bruk.