Lineare Algebra 2 ggT

Question

A=1.440.904 und b=3.835.089. Man bestimme den ggT mit Hilfe des euklidischen Algorithmus und bestimme r1,r2 e Z mit ar1 + br2 =c

Answer 1

Rekursive Lösung für ggT ( a , b ) mit a ≥ b:

ggT ( a, b )

= a falls b = 0

= ggT ( b , a mod b ) sonst

 

Damit ergibt sich:

ggT ( 3.835.089 , 1.440.904 )

b ≠ 0 , also:

= ggT( 1.440.904 , 3.835.089 mod 1.440.904 ) = ggT( 1.440.904 , 953281 )

b ≠ 0 , also:

= ggT( 953281 , 1.440.904 mod 953281 ) = ggT( 953281 , 487623 )

= ggT( 487623 , 953281 mod 487623 ) = ggT ( 487623 , 465658 )

= ggT ( 465658 , 487623 mod 465658 ) = ggT ( 465658 , 21965 )

= ggT ( 21965 , 465658 mod 21965 ) = ggT ( 21965 , 4393 )

= ggT ( 4393 , 21965 mod 4393 ) = ggT ( 4393 , 0 )

b = 0 , also:

= 4393

 

und bestimme r1,r2 e Z mit ar1 + br2 =c

Das verstehe ich nicht so recht. Was ist c ?

Answer 2

3835089 / 1440904 = 2 R 953281

1440904 / 953281 = 1 R 487623

953281 / 487623 = 1 R 465658

487623 / 465658 = 1 R 21965

465658 / 21965 = 21 R 4393

21965 / 4393 = 5 R 0

ggT = 4393

Kannst du den 2. Teil jetzt alleine machen?