Joachim Mohr   Mathematik Musik Delphi
≡

Satz

Haben a und #iii# einen gemeinsamen Teiler k, dann auch a-b und #iii# und dann auch a-2b und #iii# usw.
Beweis: a=k·a1 und b=k·b1, dann ist a-b=k·(a1-b1), also a-b hat auch den Teiler k.
Es gilt also für den größten gemeinsamen Teiler von a und b die Gleichung ggT(a,b)=ggT(a-q·b,k), falls a:b=q mit Rest r.

Euklidischer Algorithmus

Der Euklidischer Algorithmus ermöglicht die Berechnung des ggT, des größten gemeinsamen Teilers.
Der ggT(a,b) wird folgendermaßen berechnet:

Berechnung des ggT(a,b)

Setzte r0=a und r1=b 
r0:r1=q1 Rest r2. Ist r2=0, dann ist ggT(a,b)=r1.
r1:r2=q2 Rest r3. Ist r3=0, dann ist ggT(a,b)=r2.
r2:r3=q3 Rest r4. Ist r4=0, dann ist ggT(a,b)=r3.
usw.

Beispiel bei natürlichen Zahlen

Gesucht: ggT(1071,462) 
1071:462=2 Rest 147
462:147=3 Rest 21 
147:21=7 Rest 0, also ggT(1071,462)=21

Gesucht: ggT(17017,3519) 
17017:3519=4 Rest 2941
3519:2941=1 Rest 578
2941:578=5 Rest 51
578:51=11 Rest 17
51:17=3 Rest 0 also ggT(1717,3519)=17

Beispiel bei Polynomen

Satz: Hat das Polynom p eine doppelte Nullstelle x0, dann hat p' die Nullstelle x0. 
                         2
Beweis: p(x)=p1(x)·(x-x0) ⇒ 


                   2
p'(x)=p1'(x)·(x-x0) + 2p1(x)(x-x0)=(x-x0)·(p1'(x)(x-x0)+2p1(x)).

Also: ggT(p,p') enthält den Faktor (x-x0).




                    3   2                 
1. Beispiel: p(x)=(x -5x +8x-4); 

                      2 
             p'(x)=(3x -10x+8)





Die 1. Polynomdivision: r0:r1=q1 Rest r2
 (x^3-5x^2+8x-4):(3x^2-10x+8) = 1/3x-5/9 Rest -2/9x+4/9=-2/9(x-2)
-(x^3-10/3x^2+8/3x)
----------------------
-5/3x^2+16/3x-4
-(-5/3x^2+50/9x-40/9)
----------------------
-2/9x+4/9

Die 2. Polynomdivision: r1:r2=q2 Rest r3
 (3x^2-10x+8):(x-2) = 3x-4 Rest 0
-(3x^2-6x)
----------------------
-4x+8
-(-4x+8)
----------------------
0



                    3   2        2
Also ggT(p,p')=ggT(x -5x +8x-4,3x -10x+8)=x-2.

d.h. x-2 ist doppelte Nullstelle von p.



 

                   4   2
2. Beispiel: p(x)=x +2x +1

        3
P'(x)=4x +4x





Die 1. Polynomdivision: r0:r1=q1 Rest r2
 (x^4+2x^2+1):(4x^3+4x) = 1/4x Rest x^2+1
-(x^4+x^2)
----------------------
x^2+1

Die 2. Polynomdivision: r1:r2=q2 Rest r3
 (4x^3+4x):(x^2+1) = 4x Rest 0
-(4x^3+4x)
----------------------
0




                    4   2     3       2
Also ggT(p,p')=ggT(x +2x +1,4x + 4x)=x +1 

      2
d.h. x +1 = (x+i)(x-i)  ⇒ x=-i und x=+i sind doppelte Nullstellen von p.



Es ist nämlich


      4   2     2   2
p(x)=x +2x +1=(x +1)



und 

        3        2
P'(x)=4x +4x=4x(x +1)




   ↑