ggT mit extrem großen Zahlen

Question

Aufgabe:

\( g g T\left(10^{100}+50,10^{99}+2\right) \)

Problem/Ansatz:

Meine Lösung: da (10^99) +2 eine 0 weniger hat als (10^100)+50 passt es 10 mal in 100^100+50   50 - (10*2) = 30 also rest 30

10^99+2 : 30, wenn 10002 : 30 = 333 rest 12 ist 100003 : 30 = 3333 rest 12 kann man dann so weiter führen und

(10^99)+2 : 30 = 33...33 (98 Stellen) rest 12

30 : 12 = 2 rest 6

12 : 6 = 0 rest 6 also ist der ggT  = 6 , aber irgendwie habe ich das Gefühl das es auch einfacher geht und ich mir den anstrengenden Weg ausgesucht habe.

Answer 1

Der ggT von zwei Zahlen ist auch der ggT der Differenz dieser Zahlen (das ist die Grundlage des Euklidischen Algorithmus).

Daraus folgt

\(ggT\left(10^{100}+50,10^{99}+2\right)\)=\(ggT\left(9\cdot 10^{99}+48,10^{99}+2\right)\)

Kommst du damit weiter?

Comments

Sei nicht so voreilig mit deinen Bewertungen ("Beste Antwort").

Die von Tschaka ist besser (jedenfalls habe ich ihm einen Pluspunkt gegeben).

Answer 2

Aloha :)

$$\frac{10^{100}+50}{10^{99}+2}=\frac{10\cdot10^{99}+10\cdot2+30}{10^{99}+2}=10+\frac{30}{10^{99}+2}$$Wir brauchen also nur noch den ggT von \(10^{99}+2\) und \(30\) zu bestimmen. \(10^{99}+2\) ist gerade und hat die Quersumme \(3\), ist also durch \(6\) teilbar. Dasselbe gilt für die \(30\), die damit auch durch \(6\) teilbar ist. Da \(\frac{10^{99}+2}{3}\) nicht auf einer \(5\) oder auf einer \(0\) endet, ist der Bruch nicht durch \(5\) teilbar. Damit ist \(6\) der gesuchte ggT.

Answer 3

Hallo,

\( 10^{100} + 50 = 10 (10^{99} + 5) \) hinterlässt bei Division durch \( 10^{99} + 2 \) den Rest \( -30 \), wie man leicht überprüft. Es ist also \( \textrm{ggT}( 10 (10^{99} + 5), 10^{99} + 2) = \textrm{ggT}(-30, 10^{99} + 2) \).

Um den Rest von \( 10^{99} + 2 \) bei Division durch \( -30 \) zu ergründen, betrachten wir: Die Teilbarkeit durch \( -30 = - 5 \cdot 3 \cdot 2 \) impliziert die Teilbarkeit durch \( 5 \), \( 3 \) und \( 2 \). \( 10^{99} + 20 \) ist eine durch diese drei Zahlen teilbare Zahl, denn ihre Quersumme \( 3 \) zeigt die Teilbarkeit durch \( 3 \), ihre letzte Ziffer \( 0 \) zeigt die Teilbarkeit durch \( 5 \) und \( 2 \).

Wir erhalten \( \textrm{ggT}(-30, 10^{99} + 2) = \textrm{ggT}(-30, -18) = 6 \).

Grüße

Mister