Baustein:Größter gemeinsamer Teiler

Aus VoWi
(Weitergeleitet von Baustein:GgT)
Wechseln zu: Navigation, Suche

Größter gemeinsamer Teiler[Bearbeiten, WP, 1.14 Definition]

Der größte gemeinsame Teiler (ggT) von zwei ganzen Zahlen a und b ist die größte positive natürliche Zahl, die Teiler beider Zahlen ist.

Die Vielfachheit jeder Primzahl p im größten gemeinsamen Teiler entspricht dem Minimum der Vielfachheiten von p in a und b.

\textrm{ggT}(a, b) := \prod_{p \in \mathbb{P}} p^{\min(\nu_p(a), \; \nu_p(b))}