Theorem - m teilt n implies m ist ggT von m und n

• Involvierte Definitionen:
  • ggT
  • Teilbarkeit
• Veranstaltung: AlgoMathe
• Referenz: @ziegenbalg2015

⠀

Theorem: teilt

Seien .
Sei Teiler von (also ).

Dann gilt:

Beweis

Sei .

Es gilt: . In anderen Worten: jede Zahl, die teilt, ist entweder selbst oder kleiner als .

Damit ist der größte Teiler von . Daher gilt auch .

Da also der größte Teiler von ist und außerdem auch ein Teiler von ist, ist auch der , was zu zeigen war.