Wie finde ich den ggt einer zahlenmenge heraus?

Question

Ich nehme eine vierstellige zahl und schreibe diese zweimal hintereinander so dass sie acht-stellig wird.
z.b. 2345 -> 23452345 nun will ich den größten gemeinsamen teiler wissen
das hier habe ich im internet dazu gefunden, verstehe es aber nicht:

"Der Satz von Euklid lässt sich zur Anwendung über einer Zahlenmenge erweitern:
x1, x2, .., xn ganze Zahlen ∧ ∀ i ∈ 1..n : xi > 0 ∧ j, k ∈ 1..n ∧ xj > xk> 0 ⇒
ggT(x1, x2, ..,xj, ..,xk, .., xn) = ggT(x1, x2, .., mod(xj, xk), ..,xk, .., xn)."

Sieben- ohrhase · Accepted Answer

Den ggT von  e i n e r   Zahl zu finden ist ziemlich schwierig.

Welche andere Zahl willst Du denn neben 23452345 noch untersuchen.


Wo genau hast Du Das mit dem '..Satz des Euklid..... Zahlemmenge.....' gefunden ?, bitte genaue URL-Angabe

So wie es hier kopiert ist, ist es kaum lesbar.

-------------------------------------------------------------------------------
Der groesste gemeinsame Teiler der Menge aller Zahlen, die durch diese Vorschrift entstehen ist 10001.

a. 10001 ist Teiler aller dieser Zahlen, das ist durch das Bildungsgesetz klar:
 A = abcdabcd = 10000 * abcd + abcd = 10001 * abcd 

b. zumindest die Zahlen 12371237 und 12491249 haben keinen weiteren Teiler, denn sowohl 1237 als auch 1249 sind Primzahlen und somit lassen sie ausser 10001*1237 bzw 10001*1245 keine weitere Faktorenzerlegung zu.

Damit ist die Behauptung bewiesen.

--------------------------------------------------------------------------

Die Sache mit Euklid werde ich nachher mal lesen, hier wird sie nicht benötigt,

sindy00_00 · Answer

Ich verstehe nicht genau von was du den grÃ¶Ãten gemeinsamen Teiler wissen willst, denn du hast ja nur eine Zahl. Du brauchst aber mindestens zwei Zahlen um den ggT herauszufinden.

Wenn du die Zahl zweimal hintereinander schreibst hast du ja nur eine Zahl. Mit welcher willst du jetzt den ggT wissen?

Eine einfache Methode wÃ¤re die Teilermengen zu vergleichen ist aber bei acht stelligen Zahlen ziemlich aufwendig.
Bsp: 14 hat die Teilermenge {1,2,7,14}; 24 hat die Teilermenge{1,2,3,4,6,8,12,24}. Die grÃ¶Ãte Zahl, die in beiden Teilermengen enthalten ist, ist die 2; also ist 2 der ggT von 14 und 24.
Wie gesagt, bei achtstelligen Zahlen irgendwie doof.

Alternativ kann man den grÃ¶Ãten gemeinsamen Teiler zweier Zahlen auch berechnen, indem man die Primfaktorzerlegung der beiden Zahlen vergleicht. Der grÃ¶Ãte gemeinsame Teiler ist dann das Produkt aus all den gemeinsamen Primfaktoren der beiden Zahlen.
Aber auch das ist bei einer 8 Stelligen Zahl fast unmÃ¶glich, auÃer du hast eine Primzahlentabelle oder ein Computerprogramm. Denn Primzahlen kann man nicht berechnen.

euklidischer Algorithmus
Beim euklidischen Algorithmus wird in aufeinanderfolgenden Schritten jeweils eine Division mit Rest durchgefÃ¼hrt, wobei der Rest im nÃ¤chsten Schritt zum neuen Divisor wird. Der Divisor, bei dem sich Rest 0 ergibt, ist der grÃ¶Ãte gemeinsame Teiler der Ausgangszahlen. Beispiel:
1071:1029 = 1 Rest 42
1029:42 =24 Rest 21 (du kannst auch 7071 nehmen, es kommt das gleiche raus)
42:21=2 Rest 0

Somit ist 21 der grÃ¶Ãte gemeinsame Teiler von 1071 und 1029.

Ich nehm jetzt mal deine Zahl 23452345 und noch eine z.B. 34563456

34563456 : 23452345 = 1 Rest: 11111111
23452345 : 11111111 = 2 Rest: 1230123
11111111: 1230123   = 9 Rest: 40004
1230123  : 40004      = 30 Rest: 30003
40004     : 30003      = 1 Rest: 10001
30003     : 10001      = 3 Rest 0

Somit ist 3 der ggt von 34563456 und 23452345 

Kannst du alles ganz simpel mit dem Taschenrechner machen.
D.h. du gibst die Zahlen die du Teilen willst in Taschenrechner ein. Die Ganze Zahl vor deinem Komma ist as Ergebnis. Den Rest bekommst du in dem du  dann wieder die Zahl eingibst und minus die zweite zahl und diese mal das Ergebnis, dann hast du den Rest.

Beispiel zur Rechnung:
1230123  : 40004   in den Taschenrechner eingeben Ergebnsi: 30,75 also ist hier 30 dein Ergebnis. Dann brauchst noch den Rest:
1230123 - (40004*30) in den Taschenrechner eingeben (da Punkt vor Strich gilt brauchst die Klammer nicht, hab se nur zur Verdeutlichung hingeschrieben) Ergebnis: 300003 jetzt haÃt du deinen Rest.

Viel SpaÃ beim Rechnen, wenn man es weiÃ ist es ganz einfach

Wie finde ich den ggt einer zahlenmenge heraus?

2 Antworten