gmp_gcd — Funktion · PHP-Referenz

Signatur

gmp_gcd(GMP|int|string $num1, GMP|int|string $num2): GMP

Beschreibung

gmp_gcd ermittelt den größten gemeinsamen Teiler (ggT, englisch: greatest common divisor) zweier ganzer Zahlen. Der ggT ist die größte positive ganze Zahl, die beide Zahlen ohne Rest teilt. Das Ergebnis ist immer nicht-negativ, auch wenn einer oder beide Eingabewerte negativ sind.

Die Funktion arbeitet intern mit dem Euklidischen Algorithmus und kann mit beliebig großen Zahlen umgehen, die das GMP-Format erlaubt — weit über die Grenzen nativer PHP-Integers hinaus. Die Parameter können als GMP-Objekte, native PHP-Integer oder als numerische Strings übergeben werden.

Typische Anwendungsfälle sind die Kürzung von Brüchen, kryptografische Berechnungen (z. B. RSA-Schlüsselerzeugung), Prüfung auf Teilerfremdheit (gmp_gcd($a, $b) == 1) sowie allgemeine zahlentheoretische Aufgaben.

Parameter

Name	Typ	Default	Beschreibung
$num1 Pflicht	GMP\|int\|string		Erste ganze Zahl als GMP-Objekt, PHP-Integer oder numerischer String (auch sehr große Zahlen möglich).
$num2 Pflicht	GMP\|int\|string		Zweite ganze Zahl als GMP-Objekt, PHP-Integer oder numerischer String.

Rückgabewert

Typ

GMP

Beschreibung

Gibt ein GMP-Objekt zurück, das den größten gemeinsamen Teiler beider Eingabewerte repräsentiert. Das Ergebnis ist stets nicht-negativ. Wenn beide Eingaben 0 sind, ist der Rückgabewert ebenfalls 0.

Beispiele

Einfacher ggT zweier ganzer Zahlen

<?php
$result = gmp_gcd(48, 18);
echo gmp_strval($result); // Ausgabe: 6

// Teilerfremdheit prüfen
$a = 35;
$b = 64;
$gcd = gmp_gcd($a, $b);
if (gmp_cmp($gcd, 1) === 0) {
    echo "$a und $b sind teilerfremd.";
} else {
    echo "ggT von $a und $b ist " . gmp_strval($gcd);
}

6 35 und 64 sind teilerfremd.

Bruch kürzen mit gmp_gcd

<?php
// Bruch 84/126 kürzen
$zaehler   = gmp_init(84);
$nenner    = gmp_init(126);
$gcd       = gmp_gcd($zaehler, $nenner);

$zaehler_gekuerzt = gmp_div_q($zaehler, $gcd);
$nenner_gekuerzt  = gmp_div_q($nenner,  $gcd);

echo gmp_strval($zaehler_gekuerzt) . '/' . gmp_strval($nenner_gekuerzt);

2/3

ggT sehr großer Zahlen (jenseits nativer PHP-Integer)

<?php
// Sehr große Zahlen als Strings übergeben
$a = '123456789012345678901234567890';
$b = '987654321098765432109876543210';

$gcd = gmp_gcd($a, $b);
echo gmp_strval($gcd);

90000000009000000000900000000090

// Wichtig · Fallstricke

Vorzeichen: Das Ergebnis von gmp_gcd ist immer nicht-negativ, unabhängig von den Vorzeichen der Eingaben. gmp_gcd(-12, 8) ergibt also 4, nicht -4.

Nullwerte: gmp_gcd(0, n) ergibt |n|, da jede Zahl 0 teilt. Nur gmp_gcd(0, 0) liefert 0.

Voraussetzung: Die GMP-Extension muss aktiviert sein (PHP mit --with-gmp kompiliert oder entsprechende Extension geladen). Für sehr große RSA-Schlüssel oder kryptografische Berechnungen sollte zusätzlich auf sicherheitszertifizierte Bibliotheken gesetzt werden.

Siehe auch

gmp_lcm gmp_invert gmp_div_q gmp_init gmp_strval