matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Hochschulmathe
  Status Uni-Analysis
    Status Reelle Analysis
    Status UKomplx
    Status Uni-Kompl. Analysis
    Status Differentialgl.
    Status Maß/Integrat-Theorie
    Status Funktionalanalysis
    Status Transformationen
    Status UAnaSon
  Status Uni-Lin. Algebra
    Status Abbildungen
    Status ULinAGS
    Status Matrizen
    Status Determinanten
    Status Eigenwerte
    Status Skalarprodukte
    Status Moduln/Vektorraum
    Status Sonstiges
  Status Algebra+Zahlentheo.
    Status Algebra
    Status Zahlentheorie
  Status Diskrete Mathematik
    Status Diskrete Optimierung
    Status Graphentheorie
    Status Operations Research
    Status Relationen
  Status Fachdidaktik
  Status Finanz+Versicherung
    Status Uni-Finanzmathematik
    Status Uni-Versicherungsmat
  Status Logik+Mengenlehre
    Status Logik
    Status Mengenlehre
  Status Numerik
    Status Lin. Gleich.-systeme
    Status Nichtlineare Gleich.
    Status Interpol.+Approx.
    Status Integr.+Differenz.
    Status Eigenwertprobleme
    Status DGL
  Status Uni-Stochastik
    Status Kombinatorik
    Status math. Statistik
    Status Statistik (Anwend.)
    Status stoch. Analysis
    Status stoch. Prozesse
    Status Wahrscheinlichkeitstheorie
  Status Topologie+Geometrie
  Status Uni-Sonstiges

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenZahlentheorieErste 3 Dez.-Stellen 2^64
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Zahlentheorie" - Erste 3 Dez.-Stellen 2^64
Erste 3 Dez.-Stellen 2^64 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Erste 3 Dez.-Stellen 2^64: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 19:43 Sa 16.09.2006
Autor: subclasser

Aufgabe
Wie lauten die ersten drei Dezimalstellen (von links) der Zahl [mm] $2^{64} [/mm] - 1$?

Hallo allerseits!

Vor kurzem tauchte in einer Aufgabe die Frage nach den drei größten Dezimalstellen der Zahl [mm] $2^{64} [/mm] - 1$ auf.
Mit einem Taschenrechner lässt sich diese Aufgabe natürlich schnell lösen.
Ich habe mich jedoch gefragt, ob es auch eine Möglichkeit gibt, diese drei Ziffern ohne technische Hilfsmittel oder massenhaftes stures Multiplizieren zu bekommen. Leider bin ich auf keinen grünen Zweig gekommen.

Die einzige (etwas magere) Idee war die folgende:

Gebe $d(n) [mm] \; \forall \, [/mm] n [mm] \left\{ n \in \mathbb{N} \mid n \geq 100 \right\}$ [/mm] die ersten drei Dezimalstellen der Zahl $n$ an. Es gilt

$$10 [mm] \nmid 2^{64} \Rightarrow d(2^{64}-1) [/mm] = [mm] d(2^{64})$$ [/mm]
Zudem ist

[mm] $$d(2^{n+1}) [/mm] = 2 [mm] \cdot d(2^n) \; \vee \; d(2^{n+1}) [/mm] = 2 [mm] \cdot d(2^n) [/mm] + 1 [mm] \; \forall \, d(2^n) [/mm] < 500$$
Für größere [mm] $d(2^n)$ [/mm] müsste man noch beachten, dass die letzte Ziffer gestrichen werden muss (dies ließe sich natürlich auch noch formulieren ;-)).

Jetzt kommt das große Problem: Mir ist es unmöglich festzustellen, welche der beiden Fälle eintritt.
Ich entdecke bei den kleineren Dezimalstellen, die das Verhalten beim Verdoppeln beeinflussen, keine Regelmäßigkeit.
Somit ist es mir unmöglich, die ersten drei Dezimalstellen sukzessive zu erhalten.

Für mich ist es noch ziemlich ungewohnt, mathematische Probleme formal darzustellen. Ich hoffe, es ist mir hier einigermaßen gelungen. Zudem bin ich mir nicht sicher, in welches Teilgebiet der Mathematik die Frage einzuordnen ist (wobei ich instinktiv Zahlentheorie annehme).

Ich wäre sehr dankbar, wenn ihr mir Ideen liefern könntet, wie man dieses Problem lösen könnte.

Im voraus besten Dank!

        
Bezug
Erste 3 Dez.-Stellen 2^64: Antwort
Status: (Antwort) fertig Status 
Datum: 20:16 Sa 16.09.2006
Autor: EvenSteven

Hoi
Der entscheidende Begriff hier ist die Rechenoperation modulo. Wenn du eine ganze Zahl modulo einer anderen rechnest, ergibt das den Rest bei der normalen Division.

Bsp.

$17 [mm] \mod [/mm] 6 = 5$ denn $17:6=2 [mm] \mbox{ Rest } [/mm] 5$
$56205252 [mm] \mod [/mm] 1000 = 252$

Letzeres Beispiel zeigt dir, dass du die letzten drei Ziffern einer Zahl kriegst, wenn du mod 1000 rechnest. D.h. deine Frage reduziert sich auf:

Was ist [mm] $2^{64}-1 \mod [/mm] 1000$ ?

Bei der modulo-Operation gibt es eine ganz praktische Rechenregel für dieses Problem:

$(a*b) [mm] \mod [/mm] m = (a [mm] \mod [/mm] m) * (b [mm] \mod [/mm] m)$

Wenn ich mehr sage, ist das Problem schon fast gelöst :-)

Gruss

EvenSteven


Bezug
                
Bezug
Erste 3 Dez.-Stellen 2^64: Probleme beim Reduzieren
Status: (Frage) beantwortet Status 
Datum: 11:38 So 17.09.2006
Autor: subclasser

Hallo EvenSteven,

vielen Dank für deine Hilfe. Leider hast du mein Problem falsch verstanden. Ich suchte die drei ersten Ziffern der Zahl und nicht die drei letzten.

Nichtsdestoweniger eine Rückfrage zu dem neuen Problem :-)

Folgender Lösungssatz

Wir betrachten die letzten drei Ziffern der Zahl [mm] $2^{64}$ [/mm] und ziehen anschließend $1$ ab, um die gewünschten letzten drei Ziffern zu erhalten.
Nach deiner Formel gilt

[mm] $$2^{64} \mod [/mm] 1000 = [mm] \left(\left(2^{10}\right)^6 * 2^4 \right) \mod [/mm] 1000 = [mm] 24^6 \cdot [/mm] 16$$
Das macht so keinen Sinn :-). Irgendetwas habe ich da falsch verstanden. Denn

$$30 [mm] \mod [/mm] 7 = (6 [mm] \mod [/mm] 7) [mm] \cdot [/mm] (5 [mm] \mod [/mm] 7) = 30$$
So kann bei der Multiplikation doch ein viel größerer Wert entstehen, wie es die Restgruppe zulässt?

Gruß und schönes Wochenende!


Bezug
                        
Bezug
Erste 3 Dez.-Stellen 2^64: Antwort
Status: (Antwort) fertig Status 
Datum: 12:21 So 17.09.2006
Autor: EvenSteven

Wer lesen kann, ist klar im Vorteil :-)



> Folgender Lösungssatz
>  
> Wir betrachten die letzten drei Ziffern der Zahl [mm]2^{64}[/mm] und
> ziehen anschließend [mm]1[/mm] ab, um die gewünschten letzten drei
> Ziffern zu erhalten.
>  Nach deiner Formel gilt
>  
> [mm]2^{64} \mod 1000 = \left(\left(2^{10}\right)^6 * 2^4 \right) \mod > 1000 = 24^6 \cdot 16[/mm]

Ja das am Schluss natürlich nochmals mod 1000 rechnen, dann kommt am Schluss 616 raus. D.h. wenn du das letzte mod 1000 rechnest, kannst du wieder die mod-Regel verwenden, bis du am Schluss 616 kriegst.

>  
> Das macht so keinen Sinn :-). Irgendetwas habe ich da
> falsch verstanden. Denn
>  
> [mm]30 \mod 7 = (6 \mod 7) \cdot (5 \mod 7) = 30[/mm]
>  So kann bei
> der Multiplikation doch ein viel größerer Wert entstehen,
> wie es die Restgruppe zulässt?

Das ist ja gerade ein etwas pathologisches Beispiel :-) Der Nutzen der Regel besteht viel mehr darin, eine grosse (wirklich grosse) Zahl modulo eine verhältnismässig kleine Zahl einfach zu berechnen. Nur jemand mit arg viel Zeit würde [mm] 2^{64} [/mm] ausrechnen und dann erst mod 1000 rechnen (wenn er es denn von Hand macht). Es gibt aber auch Anwendungsgebiete (z.b. Verschlüsselung), wo selbst der Computer aufgeben würde.


>  
> Gruß und schönes Wochenende!
>  

Ciao

EvenSteven

Bezug
                                
Bezug
Erste 3 Dez.-Stellen 2^64: Zusatzproblem geklärt
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:14 So 17.09.2006
Autor: subclasser

Vielen Dank EvenSteven!

Ich habe weitergerechnet und dann tatsächlich $616$ als Ergebnis herausbekommen. Damit wäre die Frage nach den letzten drei Dezimalstellen geklärt :-)

Bezug
                
Bezug
Erste 3 Dez.-Stellen 2^64: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:06 So 17.09.2006
Autor: felixf

Hallo!

> Bei der modulo-Operation gibt es eine ganz praktische
> Rechenregel für dieses Problem:
>  
> [mm](a*b) \mod m = (a \mod m) * (b \mod m)[/mm]

Wie ihr schon bemerkt habt, diese Rechenregel ist fuer die meisten Faelle falsch. Richtig lautet sie: [mm] (a * b) \mod m = ((a \mod m) * (b \mod m)) \mod m[/mm].

LG Felix


Bezug
        
Bezug
Erste 3 Dez.-Stellen 2^64: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 02:57 Mi 18.10.2006
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.unimatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]