Euclid Algorithmus für große Zahlen, Rechnungsmethode des ggT und kgV

Finde größte gemeinsame Teiler (ggT) für große Zahlen


Für große Zahlen, die Zerlegung der prima Faktor ist schwierig. Falls wir größte gemeinsame Teiler (ggT) von solche großen Zahlen feststellen wollen, dann wird eine Methode benutzt, die die Zerlegung in prim Faktor nicht vewendet, sondern es wird das Euclid Algorithmus verwendet... siehe Beispiel unten.

Sehen wir mal welche die größte gemeinsame Teiler (ggT) der Zahlen 53.667 und 25.527 ist:

Also die größte gemeinsame Teiler der zwei Zahlen ist der letzte Rest (unterschiedlich von Null, klar).

Wenn der letzte Rest gleich mit eins ist, dann sind die beiden Zahlen zwischen einander prim.

Für die obenerwähnten Operationen, die letzte Nennzahl, 201, ist größte gemeinsame Teiler (ggT) der Zahlen 53.667 und 25.527.

Mit der Hilfe des Euclid Algorithmus können wir beweisen, dass zwei Zahlen zwischen sich prim sind.

Zum Beispiel, wirs sollen suchen ggT (87, 41):

Der letzte Rest von den obiegen Operationen, nicht 0, ist gleich mit 1.

ggT (87, 41) = 1, also die Zahlen sind zwischen sich prim.

Die Anwendung des Euclid Algorithmus für mehr als zwei Zahlen:

Der Euclid Algorithmus kann auch verwendet werden, um größte gemeinsame Teiler (ggT) von mehreren Zahlen zu finden, zum Beispiel a, b und c. Es wird in Etappen gearbeitet. Zuerst werden wird ggT (a, b) = d und nacher werden wir ggT (c, d) = e.

Euclid Algorithmus: finde die kleinste gemeinsame Vielfache (kgV) für große Zahlen


Im Falle der großen Zahlen es wird unbequem die kleinste gemeinsame Vielfache (kgV) zu rechnen, weil die Division in prim Faktor zu viel Zeit braucht.

Mit der Hilfe von Euclid Algorithmus wird der größte gemeinsame Teiler gefunden (ggT) – siehe oben, aber auch die kleinste gemeinsame Vielfache (kgV), nach der Regel:

kgV (a, b) = (a × b) / ggT (a, b);

Diese Methode kann bei nicht mehr zwei Zahlen benutzt werden.


Was ist eine Primzahl?

Was ist eine zusammengesetzte Zahl?

Primzahlen bis 1.000

Primzahlen bis 10.000

Erastotene Sieb

Euclid Algorithmus

Brüche Kürzen: Schritte und Beispiele