Faktorzerlegung von Googolplex+n

20.09.2009, 16:02

Ivan33

Faktorzerlegung von Googolplex+n

Hi!

Mich beschäftigt die Frage wie es möglich ist, Googolplex+n in Faktoren zu zerlegen:

$\begin{eqnarray*} Googolplex = 10^{10^{100}} \end{eqnarray*}$

Das ist eine so hohe Zahl, dass sie nicht einmal im Dezimalsystem auf einem Computer dargestellt werden kann (zu wenig Speicherplatz).

Auf dieser Seite habe ich bekannte Faktoren von Googolplex+n gefunden: http://www.alpertron.com.ar/GOOGOL.HTM

Aber wie zum Teufel funktioniert die Zerlegung von so hohen Zahlen?

Alles durch einfache Teilbarkeitsregeln für Zahlen mit vielen Nullen?
Wenn ja; ist es leicht Teilbarkeitsregeln für große Zahlen bzw. Primzahlen zu genieren? z.B. für 316912650057057350374175801344000001 (Primfaktor von Googolplex+1)?
Wenn es nicht leicht ist; wie lange würde es durchschnittlich dauern eine Teilbarkeitsregel für eine Primzahl mit sagen wir mal 40 Stellen zu genieren? Weniger oder mehr als eine Stunde? Weniger oder mehr als ein Tag? Weniger oder mehr als ein Monat? Weniger oder mehr als ein Jahr?
Wenn nein; wie dann?

Wäre nett, wenn ihr dazu Angaben machen könntet. smile

20.09.2009, 16:10

Auf diesen Beitrag antworten »

Zitat:

Original von Ivan33
wie lange würde es durchschnittlich dauern eine Teilbarkeitsregel für eine Primzahl mit sagen wir mal 40 Stellen zu genieren? Weniger oder mehr als eine Stunde? Weniger oder mehr als ein Tag? Weniger oder mehr als ein Monat? Weniger oder mehr als ein Jahr?

Ich bezweifle, dass man an diese Frage mit der Stoppuhr herangehen kann. Zumal du mal erklären solltest, was du hier unter Teilbarkeitsregel verstehen willst?

20.09.2009, 16:16

Ivan33

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent

Zitat:

Ich bezweifle, dass man an diese Frage mit der Stoppuhr herangehen kann. Zumal du mal erklären solltest, was du hier unter Teilbarkeitsregel verstehen willst?

Eine (einfache) Regel für die Teilbarkeit einer Zahl.

Um beispielsweise zu testen ob 54209582039582039548 durch 2 teilbar ist, muss man nicht die gesamte Zahl durch 2 teilen, sondern nur die letzte Stelle beachten. Sie ist gerade. Also ist die gesamte Zahl auch gerade. Um zu testen ob 10000000011 durch 3 teilbar ist, muss man nur die Quersumme der Zahl ausrechnen, also 1+1+1 = 3. Wenn diese durch 3 teilbar ist, ist die gesamte Zahl auch durch 3 teilbar. Sagt einem die Quersumme nichts, rechnet man einfach die Quersumme der Quersumme aus, usw.

Aber wie lange es dauert eine Teilbarkeitsregel für eine Zahl zu genieren ist nicht meine Hauptfrage, sondern wie es möglich ist, Googolplex+n in Faktoren zu zerlegen.

20.09.2009, 16:22

Auf diesen Beitrag antworten »

Zitat:

Original von Ivan33
Eine (einfache) Regel für die Teilbarkeit einer Zahl.

Diese Erklärung ist vom mathematischen Standpunkt aus ziemlich wertlos.

Wenn du von "letzten Stellen" sprichst, betrachtest du zudem alles durch die Dezimalsystembrille. Äußerst schädlich, da so gut wie alle Computer etwa intern im Dualsystem rechnen, was bei so großen Zahlen einen immensen Unterschied macht, da der Aufwand zum Hin- und Herkonvertieren erheblich ist.

20.09.2009, 16:29

Ivan33

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent

Zitat:

Original von Ivan33
Eine (einfache) Regel für die Teilbarkeit einer Zahl.

Hast recht.

20.09.2009, 16:36

Auf diesen Beitrag antworten »

Na gut, dann mal eine Teilbarkeitsregel - und zwar eine Verallgemeinerung der Quersummenregel:

Für die Teilbarkeit durch Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ genügt es, von hinten beginnend jeweils Ziffernblöcke der Länge $\begin{eqnarray*} p-1 \end{eqnarray*}$ zu bilden und von diesen Blöcken die Quersumme zu bilden und die Teilbarkeit durch $\begin{eqnarray*} p \end{eqnarray*}$ zu prüfen.

Das gilt im Dualsystem für alle Primzahlen $\begin{eqnarray*} p\geq 3 \end{eqnarray*}$ , und im Dezimalsystem zumindest für $\begin{eqnarray*} p\geq 7 \end{eqnarray*}$ , der Beweis ist klar über den kleinen Fermat.

Wenn allerdings die Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ größer wird als die Stellenzahl der zu untersuchenden Zahl, dann bringt diese Regel keinen Nutzeffekt.

20.09.2009, 20:57

Ivan33

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Für die Teilbarkeit durch Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ genügt es, von hinten beginnend jeweils Ziffernblöcke der Länge $\begin{eqnarray*} p-1 \end{eqnarray*}$ zu bilden und von diesen Blöcken die Quersumme zu bilden und die Teilbarkeit durch $\begin{eqnarray*} p \end{eqnarray*}$ zu prüfen.

Wir nehmen uns ein Beispiel an der Zahl 700045653615; wir wollen prüfen ob sie durch 7 teilbar ist.

Dazu trennen wir sie in 6er-Blöcke: 700045'653615 (das meinst du doch mit Ziffernblock, oder?)
Und bilden von beiden die Quersumme: 16'26

Was jetzt? Muss ich jetzt die Teilbarkeit von 1626 prüfen? Diese Zahl ist nicht durch 7 teilbar. Aber 700045653615 ist durch 7 teilbar, weil die alternierende 3er-Quersumme (700+45-653+615 = 707) durch 7 teilbar ist.

Und wie zerlegt man Zahlen in der Form Googolplex+n in ihre Faktoren (das war meine eigentliche Frage)? Computer arbeiten doch binär. Und wenn ich meine Binärbrille anziehe, sehe ich bei Zehnerpotenzen keine Folge von Nullen nach der 1 sondern ein Wirrwarr aus Nullen und Einsen. Um von diesen Zahlen die Quersumme zu bilden, muss man also den gesamten Wert der Zahlen berechnen, was bei so hohen Zahlen unmöglich ist. Oder ist es möglich ein Programm zu schreiben, dass den Computer dezimal arbeiten lässt?

20.09.2009, 21:20

Airblader

Auf diesen Beitrag antworten »

Edit: Da hab ich mich vertippt. Sorry! Big Laugh

air

20.09.2009, 21:25

Mystic

Auf diesen Beitrag antworten »

Es ist für einen Laien vielleicht schwer vorstellbar, aber kleine Primfaktoren p von

$\begin{eqnarray*} 10^{10^{100}}+n \end{eqnarray*}$

wobei n eine "kleine" natürliche Zahl ist, lassen sich wirklich sehr leicht finden. Zunächst einmal gilt im Falle

$\begin{eqnarray*} p-1 | 10^{100} \end{eqnarray*}$

offensichtlich

$\begin{eqnarray*} 10^{10^{100}} \equiv 1 \mod p \end{eqnarray*}$

sodass obige Zahlen genau für alle n der Form n=kp-1 durch p teilbar sind. Auch der Fall p=2 und p=5 erledigt sich von selbst. Für andere p könnte man mit Hilfe der "Square and Multiply"-Methode

$\begin{eqnarray*} 10^{10^{100}} \mod p \end{eqnarray*}$

leicht direkt berechnen, wozu man gerade mal gezählte 438 modulare Multiplikationen benötigt. (Tatsächlich liegt die Rechenzeit z.B. mit DERIVE unter dessen "Wahrnehmungsschwelle" von 1 ms.) Aufgrund der Tatsache

$\begin{eqnarray*} 10 \cdot 10^{\lambda(p-1)} \equiv 10 \mod p-1 \end{eqnarray*}$

kann man weiter 100 in obigem Ausdruck ersetzen duch jeden positiven Exponenten e mit $\begin{eqnarray*} e \equiv 100 \mod \lambda(p-1) \end{eqnarray*}$ , was z.B. für p=43 mit $\begin{eqnarray*} \lambda(p-1) =6 \end{eqnarray*}$ immerhin auf die einfache Rechnung

$\begin{eqnarray*} 10^{10^{100}} \equiv 10^{10^4} \equiv -19 \mod 43 \end{eqnarray*}$

führt, d.h. für n=19+43k sind alle obigen Ausdrücke durch 43 teilbar.

20.09.2009, 21:41

Auf diesen Beitrag antworten »

Zitat:

Original von Ivan33
Dazu trennen wir sie in 6er-Blöcke: 700045'653615 (das meinst du doch mit Ziffernblock, oder?)
Und bilden von beiden die Quersumme: 16'26

Nein, das hast du falsch verstanden - wenn du dir den kleinen Fermat genauer angeschaut hättest, würdest du das auch selbst merken;

Nein, mit "Block-Quersumme" meine ich hier $\begin{eqnarray*} 700045 + 653615 = 1353660 \end{eqnarray*}$ , und wenn diese Zahl durch 7 teilbar ist, dann auch deine Ausgangszahl.

21.09.2009, 06:59

Ivan33

Auf diesen Beitrag antworten »

@Mystic Danke! Freude

@Arthur Ach so.

Neue Frage »

Antworten »

Faktorzerlegung von Googolplex+n

Verwandte Themen