Zum Inhalt springen

Euklidischer Algorithmus (Z)/ggT/3146 und 1515/Darstellung/Aufgabe/Lösung


Der euklidische Algorithmus liefert:

3146=2⋅1515+116
1515=13⋅116+7
116=16⋅7+4
7=1⋅4+3
4=1⋅3+1.

Die Zahlen 3146 und 1515 sind also teilerfremd und 1 ist ihr größter gemeinsamer Teiler. Eine Darstellung der 1 erhält man, indem man diese Division mit Rest rückwärts liest, also

1=4−1⋅3=4−(7−1⋅4)=2⋅4−7=2(116−16⋅7)−7=2⋅116−33⋅7=2⋅116−33(1515−13⋅116)=−33⋅1515+(2+13⋅33)⋅116=−33⋅1515+431⋅116=−33⋅1515+431(3146−2⋅1515)=−895⋅1515+431⋅3146.