www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

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
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
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.vorhilfe.de