Wie kann ich das ggT von großen Zahlen finden?

Erste Frage Aufrufe: 411     Aktiv: 23.09.2021 um 17:02
0
Ich habe mir einige Beispiele im Web betrachtet und weiß nicht, wie ich den ggT dieser Zahlen finden kann. Ich brauche eine effektive, einfache und schnelle Methode.

ggT(245, 343)

ggT(255,285)

Ich bin ein Anfänger! :)
Diese Frage melden
gefragt

Punkte: 12

 
Kommentar schreiben
1 Antwort
1
Kennst du den euklidischen Algorithmus? Wenn du diesen mit Teilbarkeitsregeln kombinierst sollte das relativ schnell gehen.
Diese Antwort melden
geantwortet

Student, Punkte: 10.87K

 
Könntest du mir bitte den euklidischen Algorithmus erklären? Oh, vielen Dank für die Antwort!   ─   yfoyha 23.09.2021 um 15:48
1
Du schaust wie oft die kleinere der beiden Zahlen in die größere Zahl passt und notierst den Rest. Danach machst du das mit dem Rest weiter. Im ersten Fall sieht das etwa so aus:
\(343=245+98\)
\(245=2\cdot 98 + 49\)
\(98=2\cdot 49 +0\)
Also ist \(\mathrm{ggT}(343,245)=49\)   ─   mathejean 23.09.2021 um 17:00

Kommentar schreiben