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

Euclid Algorithmus: 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:

  • 1) 53.667 = 25.527 × 2 + 2.613 (ich dividiere die größte Zahl durch die kleinste Zahl)
  • 2) 25.527 = 2.613 × 9 + 2.010 (ich dividiere die kleinste Zahl durch den Rest der Operation von oben)
  • 3) 2.613 = 2.010 × 1 + 603 (ich dividiere den Rest von der ersten Operation durch den Rest von der zweiten Operation)
  • 4) 2.010 = 603 × 3 + 201 (ich dividiere den Rest von der zweiten Operation durch den Rest von der dritten Operation)
  • 5) 603 = 201 × 3 (ich teile den Rest von der dritten Operation durch den Rest von der vierten Operation); in diesem Moment gibt es keinen Rest mehr, wir hören auf, 201 ist die gesuchte Zahl

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):

  • 1) 87 = 41 × 2 + 5 (ich teile die größte Zahl durch die kleinste Zahl)
  • 2) 41 = 5 × 8 + 1 (ich teile die kleinste Zahl durch der obiegen Operation)
  • 3) 5 = 5 × 1 (ich teile den Rest von der ersten Operation durch den Rest von der zweiten Operation, der aber eins ist, so dass die Operation keinen Rest mehr enthält)

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 Nummer?

Primzahlen bis 1.000

Primzahlen bis 10.000

Erastotene Sieb

Euclid Algorithmus

Reduzieren gewöhnlichen Mathematik Fraktionen Bedingungen zu senken (vereinfacht): Schritte und Beispielen