Definition - Größter gemeinsamer Teiler

• Konstrukte:
  • Periode einer zeithomogenen Markovkette
• Eigenschaften:
  • Ist der ggT gleich 1 so sind die Zahlen teilerfremd
  • Kommutativität des ggT
  • Theorem - m teilt n implies m ist ggT von m und n
  • Theorem - m größer n impliziert ggT(a b) = ggT(a-b b)
  • Aufgabe - ggT(2^{n} - 1, 2^{m} - 1) = 2^{ggT(n, m)} - 1
• Involvierte Definitionen:
  • Teilbarkeits-Relation
  • Regeln der Bruchrechnung
• Veranstaltung: AlgoMathe, MatheDS
• Referenz: @herzogWiSe22, @riedel2023 (Definition 7.3.29)

⠀

Definition: Größter gemeinsamer Teiler

Seien .

Als größten gemeinsamen Teiler von und bezeichnen wir mit:

Das heißt, ist

• entweder die größte natürliche Zahl, die sowohl als auch ohne Rest teilt
• oder .

Definition: Größter gemeinsamer Teiler mehrerer Zahlen

Sei eine Folge mit .

Als größten gemeinsamen Teiler von definieren wir

ü