www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

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
Forum "Zahlentheorie" - 3^1037-3 welcher Rest ?
3^1037-3 welcher Rest ? < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

3^1037-3 welcher Rest ?: Tipp Rückfrage
Status: (Frage) beantwortet Status 
Datum: 16:41 Mi 10.12.2008
Autor: svcds

Aufgabe
Welchen Rest lässt 3^1037 - 3 bei Division durch 1037?

Hi,

also ich sitz an der Aufgabe und hab am Ende 680 heraus. Hab eben immer ersetzt.

1. [mm] 3^7 [/mm] = 12 mod 1037 dann die 12 für die [mm] 3^7 [/mm] ersetzt usw.

Ist dieses Vorgehen richtig?

lg svcds

        
Bezug
3^1037-3 welcher Rest ?: Antwort
Status: (Antwort) fertig Status 
Datum: 19:12 Mi 10.12.2008
Autor: MathePower

Hallo svcds,

> Welchen Rest lässt 3^1037 - 3 bei Division durch 1037?
>  Hi,
>  
> also ich sitz an der Aufgabe und hab am Ende 680 heraus.
> Hab eben immer ersetzt.
>  
> 1. [mm]3^7[/mm] = 12 mod 1037 dann die 12 für die [mm]3^7[/mm] ersetzt usw.
>  
> Ist dieses Vorgehen richtig?


Kann ich nicht beurteilen, da die Rechenschritte fehlen.

Das Ergebnis stimmt aber trotzdem nicht.

Da 1037=17*61 berechne

[mm]3^{1037}-3 \equiv \ b_{1} \ \left(17\right)[/mm]
[mm]3^{1037}-3 \equiv \ b_{2} \ \left(61\right)[/mm]

Dies ist gleichwertig mit

[mm]x \equiv \ b_{1} \ \left(17\right)[/mm]
[mm]x \equiv \ b_{2} \ \left(61\right)[/mm]

Danach kannst Du auf diese simultane Kongruenz
mit Hilfe des []  Chinesischen Restsatzes lösen.


>  
> lg svcds


Gruß
MathePower

Bezug
                
Bezug
3^1037-3 welcher Rest ?: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:30 Mi 10.12.2008
Autor: svcds

hast du irgendwo ein beispiel, kam in der vorlesung nicht so zurecht.

kann natürlich ruhig ein anderes beispiel sein.

heißt das, dass ich z.b. die 1037 in 3^(61*17) zerteilen kann oder wie mach ich das dann?

ich bräuchte ein Beispiel oder den 1. Schritt.

Bezug
                        
Bezug
3^1037-3 welcher Rest ?: Antwort
Status: (Antwort) fertig Status 
Datum: 19:57 Mi 10.12.2008
Autor: MathePower

Hallo svcds,

> hast du irgendwo ein beispiel, kam in der vorlesung nicht
> so zurecht.
>  
> kann natürlich ruhig ein anderes beispiel sein.
>  
> heißt das, dass ich z.b. die 1037 in 3^(61*17) zerteilen
> kann oder wie mach ich das dann?


Wie abakus in diesem Post schrieb, ist das ein Fall für den []kleinen Fermat.


>  
> ich bräuchte ein Beispiel oder den 1. Schritt.


Gruß
MathePower

Bezug
                                
Bezug
3^1037-3 welcher Rest ?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:48 Mi 10.12.2008
Autor: abakus


> Hallo svcds,
>  
> > hast du irgendwo ein beispiel, kam in der vorlesung nicht
> > so zurecht.
>  >  
> > kann natürlich ruhig ein anderes beispiel sein.
>  >  
> > heißt das, dass ich z.b. die 1037 in 3^(61*17) zerteilen
> > kann oder wie mach ich das dann?
>  
>
> Wie abakus in diesem Post
> schrieb, ist das ein Fall für den
> []kleinen Fermat.
>  
>

Hallo,
ganz so einfach ist es doch nicht, weil 1037 (entgegen meiner Vermutung) leider keine Primzahl ist.
Da wird es wohl doch mit dem Chinesischen Restesatz gemacht werden müssen.
Gruß Abakus



> >  

> > ich bräuchte ein Beispiel oder den 1. Schritt.
>
>
> Gruß
>  MathePower


Bezug
        
Bezug
3^1037-3 welcher Rest ?: Antwort
Status: (Antwort) fertig Status 
Datum: 19:36 Mi 10.12.2008
Autor: abakus


> Welchen Rest lässt 3^1037 - 3 bei Division durch 1037?
>  Hi,
>  
> also ich sitz an der Aufgabe und hab am Ende 680 heraus.
> Hab eben immer ersetzt.
>  
> 1. [mm]3^7[/mm] = 12 mod 1037 dann die 12 für die [mm]3^7[/mm] ersetzt usw.
>  
> Ist dieses Vorgehen richtig?
>  
> lg svcds

Hallo,
prüfe doch mal, ob du hier den "kleinen Satz von Fermat" anwenden kannst. Ich wette, der war Inhalt eurer Vorlesung. Wenn nicht- googeln!
Gruß Abakus


Bezug
                
Bezug
3^1037-3 welcher Rest ?: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:22 Mi 10.12.2008
Autor: svcds

ja war Inhalt der Vorlesung, aber ich hab falsch abgeschrieben, weil der prof nicht so ordentlich schreibt.

habt ihr nirgendwo ein Beispiel, an dem ich das lernen kann?

Bezug
                        
Bezug
3^1037-3 welcher Rest ?: Antwort
Status: (Antwort) fertig Status 
Datum: 20:42 Mi 10.12.2008
Autor: MathePower

Hallo svcds,

> ja war Inhalt der Vorlesung, aber ich hab falsch
> abgeschrieben, weil der prof nicht so ordentlich schreibt.
>  
> habt ihr nirgendwo ein Beispiel, an dem ich das lernen
> kann?


Berechne

[mm]4^{1199}[/mm] modulo 7

[mm]5^{1199}[/mm] modulo 13


Gruß
MathePower

Bezug
                
Bezug
3^1037-3 welcher Rest ?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:03 Mi 10.12.2008
Autor: svcds

ich soll ja herausfinden, ob 1037 prim ist oder nicht.

gibts nirgends ein kommentiertes beispiel? ich lern so am besten :(

Bezug
                        
Bezug
3^1037-3 welcher Rest ?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:10 Mi 10.12.2008
Autor: abakus


> ich soll ja herausfinden, ob 1037 prim ist oder nicht.

Hä?
Da hast doch vorhin selbst festgestellt, dass 1037=61*17 gilt.

>  
> gibts nirgends ein kommentiertes beispiel? ich lern so am
> besten :(


Bezug
                                
Bezug
3^1037-3 welcher Rest ?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:19 Mi 10.12.2008
Autor: svcds

das soll ich ja herausfinden also dass der rest dann ungleich 0 wird bei dieser Rechnung

Bezug
                        
Bezug
3^1037-3 welcher Rest ?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:24 Mi 10.12.2008
Autor: MathePower

Hallo svcds,

> ich soll ja herausfinden, ob 1037 prim ist oder nicht.
>  
> gibts nirgends ein kommentiertes beispiel? ich lern so am
> besten :(


Einfache Vorgehensweise ist die, daß Du die Zahl durch alle bekannten
Primzahlen p teilst. Das mach Du solange bist Du einen Rest 0 erhältst,
oder eben bis p*p <= 1037

Beispiel: Ist 101 prim?

Bekannte Primzahlen sind 2,3,5,7, (11).

101: 2= 50 Rest 1
101: 3= 33 Rest 2
101 :5= 20 Rest 1
101 :7= 14 Rest 3

Somit ist 101 prim.

Für große Zahlen ist das aber zu aufwendig.

Siehe auch: []Probedivision


Gruß
MathePower

Bezug
                                
Bezug
3^1037-3 welcher Rest ?: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 21:37 Mi 10.12.2008
Autor: svcds

ja so würd ich ja auch vorgehen bei kleineren zahlen, aber das muss doch irgendwie ein beispiel geben irgendwo  dazu:)

Bezug
                                        
Bezug
3^1037-3 welcher Rest ?: Antwort
Status: (Antwort) fertig Status 
Datum: 22:22 Mi 10.12.2008
Autor: abakus


> ja so würd ich ja auch vorgehen bei kleineren zahlen, aber
> das muss doch irgendwie ein beispiel geben irgendwo  dazu:)

Hallo,
1037 liegt in der Nähe von 1024, ist also - rund gerechnet - etwa [mm] 32^2. [/mm]
Wenn 1037 das Produkt von zwei verschedenen Faktoren sein soll, kann einer der beiden Faktoren zwar größer als 32 sein, der andere Faktor muss dafür kleiner als 32 sein.
Es reicht also aus, wenn du für 1037 nach Primfaktoren suchst, die kleiner als 32 sind. Da kommen ja nur 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 und 31 in Frage. Die sind schnell durchgetestet.
Gruß Abakus

Bezug
                                                
Bezug
3^1037-3 welcher Rest ?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 23:28 Mi 10.12.2008
Autor: svcds

also ich probier das mal aus und meld mich dann nochmal

Bezug
                        
Bezug
3^1037-3 welcher Rest ?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:07 Do 11.12.2008
Autor: felixf

Hallo

> ich soll ja herausfinden, ob 1037 prim ist oder nicht.

Das ist der sogenannte Fermattest; hier testest du, ob 1037 eine 3-Pseudoprimzahl ist; jede Primzahl ist eine 3-Pseudoprimzahl, also wenn es keine 3-Pseudoprimzahl ist, dann kann es auch keine Primzahl sein.

Siehe auch []hier.

LG Felix


Bezug
        
Bezug
3^1037-3 welcher Rest ?: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 11:36 Do 11.12.2008
Autor: svcds

kann es sein, dass es nicht DIE Lösung gibt?

Wenn da r=0 herauskäm, wär ja alles klar....

Bei uns im Vorlesungsforum kommen die unterschiedlichsten Reste raus.

Ich poste mal eben meine Rechnungen:
http://s10.directupload.net/file/d/1640/yx5k7cpw_jpg.htm

Bezug
                
Bezug
3^1037-3 welcher Rest ?: Antwort
Status: (Antwort) fertig Status 
Datum: 11:45 Do 11.12.2008
Autor: angela.h.b.


> kann es sein, dass es nicht DIE Lösung gibt?

Hallo,

bezogen auf das Leben so ganz im allgemeinen  hast Du mit dieser Vermutung sicher recht...

Aber es gibt für [mm] 3^{1037} [/mm] - 3   sicher nur genau eine Zahl r mit [mm] 0\le r\le [/mm] 1036, die den Rest bei Division durch 1037  bildet.

Wenn ich sage, daß 35 bei Division durch 13 den Rest 5 läßt und Du behauptest, daß der Rest 7 beträgt, ist doch sofort klar, daß mindestens einer von uns unrecht hat.


> Bei uns im Vorlesungsforum kommen die unterschiedlichsten
> Reste raus.

Deutet auf Fehler verschiedenster Natur hin.

>  
> Ich poste mal eben meine Rechnungen:

Man sieht nix.

Gruß v. Angela


Bezug
                        
Bezug
3^1037-3 welcher Rest ?: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:48 Do 11.12.2008
Autor: svcds

Dann lügen wir wohl beide :D:D denn 35 durch 13 = 2 Rest 9

http://s10.directupload.net/file/d/1640/yx5k7cpw_jpg.htm


will nur wissen, wo der Fehler sein soll :)

na ja aber wenn man [mm] 3^7 [/mm] ausklammert oder [mm] 3^8 [/mm] kommt ja was anderes raus...

Bezug
        
Bezug
3^1037-3 welcher Rest ?: Antwort
Status: (Antwort) fertig Status 
Datum: 14:20 Do 11.12.2008
Autor: reverend

Ich habe zwar alle Posts gelesen, setze aber doch noch einmal vorn an.

Die Aufgabenstellung ist eine klare Übungsaufgabe zum schon mehrfach angegebenen "kleinen Fermat", einem recht effektiven Primzahltest.

Ist p eine Primzahl, dann gilt für jede zu p teilerfremde Basis a:
[mm] a^{p-1}\equiv1\mod{p} [/mm]

Diese übliche Formulierung des Satzes lässt sich natürlich auch anders schreiben:
[mm] a^p\equiv a\mod{p} [/mm] oder [mm] a^p-a\equiv0\mod{p} [/mm]

Die letzte Form hast Du hier vorliegen.

Bevor ich mal an die Rechnung gehe, eine kurze Vorüberlegung und ein paar Informationen. Die zu untersuchende Zahl heiße n, geprüft wird nun, ob eine der obigen Darstellungen wahr ist, hier also [mm] a^n-a\equiv r\mod{n} [/mm] mit a=3, n=1037 und r=0. r ist vergleichsweise einfach zu ermitteln.

Mögliche Ergebnisse:
[mm] r\not=0 \Rightarrow n\not\in\IP [/mm]
r=0 [mm] \Rightarrow [/mm] keine Aussage möglich, weitere Tests nötig

Es gibt sogenannte []Pseudoprimzahlen, die den kleinen Fermat zu einer Basis oder sogar mehreren Basen bestehen. Links zu Besonderheiten findest Du im angegebenen Artikel. Besonders interessant finde ich die Carmichael-Zahlen und die starken Pseudoprimzahlen (wg. ihrer Anwendung im Miller-Rabin-Test).

Also ermitteln wir r, ich gehe dabei Deine Rechnung ein bisschen entlang. Das wäre einfacher, wenn Du nicht nur einen Scan gepostet hättest, weil ich dann einfach hier kopieren, markieren und ggf. ändern könnte.
Glücklicherweise (für mich) brauchen wir Deine Vorlage aber auch gar nicht lange:

Du stellst fest:

> [mm] 3^7\equiv12\mod{1037} [/mm]

Das ist falsch und der Rest der (sonst im Prinzip richtig durchgeführten) Rechnung damit auch.

[mm] 3^7=2187\equiv113\mod{1037} [/mm]

Zur Vereinfachung der Rechnung suchen wir nun eine Potenz mit besonders kleinem Rest (am besten natürlich 1).

Die inzwischen bekannte Zerlegung 17*61 nutzen wir nur deswegen nicht, weil sie den Test ja ad absurdum führen würde: wozu soll ich eine Zahl mit dem kleinen Fermat überprüfen, wenn ich schon weiß, dass sie zusammengesetzt ist?

113 ist kein so kleiner Rest. Zu Fuß ist man eine Weile unterwegs, bis sich endlich etwas findet. Leider ist die Freude noch verfrüht:
[mm] 3^{33}\equiv88\mod{1037} [/mm]
[mm] 3^{59}\equiv41\mod{1037} [/mm]
[mm] 3^{62}\equiv70\mod{1037} [/mm]
Nur diese drei und natürlich [mm] 3^1,3^2,3^3,3^4 [/mm] lassen Reste unter 100.

Mit Hilfe eines kleinen Programms lassen sich diese Reste schnell berechnen, und es findet sich nach einer weiteren Durststrecke endlich das Gewünschte:

[mm] 3^{80}\equiv1\mod{1037} [/mm]

Daraus folgt auch, dass [mm] 3^{1040}=\left(3^{80}\right)^{13}\equiv1\mod{1037} [/mm]
Man kann schon sicher sagen (und leicht zeigen), dass der zu untersuchende Term [mm] 3^{1037}-3 [/mm] die Bedingung nicht erfüllen wird, aber gesucht ist hier ja das genaue Ergebnis.

Einige der bisherigen Ergebnisse sind nützlich, um Rechenzeit zu sparen:
[mm] 3^{1037}=3^{80*12+77}=\left(3^{80}\right)^{12}*3^{62+\red{12}+3}\equiv1^{12}*3^{62}*\red{3^{12}}*3^3\equiv70*\red{113}*27\equiv\red{213570\equiv985\mod{1037}} [/mm]
edit: der rote Teil ist darin falsch, dass [mm] \blue{3^{12}} [/mm] noch gar nicht berechnet war und stattdessen fälschlich die Restklassenkongruenz von [mm] \blue{3^7} [/mm] eingesetzt wurde. Richtig ist das folgende:

[mm] \blue{3^{77}=3^{62+7+7+1}=3^{62}*(3^7)^2*3\equiv70*113^2*3\equiv2681490\equiv845\mod{1037}} [/mm]

Nun ist noch die 3 abzuziehen, und insgesamt erhält man:

[mm] \blue{3^{1037}-3\equiv842\mod{1037}} [/mm]

Ergebnis: 1037 ist nicht prim. :-)

Bezug
                
Bezug
3^1037-3 welcher Rest ?: Zufälle gibt's...
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:23 Do 11.12.2008
Autor: reverend

Ich bekomme gerade angezeigt, dass der lange Beitrag eben insgesamt mein 1036. Artikel war.

Dann ist dies der 1037.
[huepf]

Bezug
                        
Bezug
3^1037-3 welcher Rest ?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:33 Do 11.12.2008
Autor: Al-Chwarizmi


> Ich bekomme gerade angezeigt, dass der lange Beitrag eben
> insgesamt mein 1036. Artikel war.
>  
> Dann ist dies der 1037.
>  [huepf]



Und das innert 44 Tagen !

Nach Adam Ries hast du also während deiner Zeit
im MatheRaum durchschnittlich jede Stunde einen
Artikel verfasst. Alle Achtung !   [applaus]    Al


Bezug
                                
Bezug
3^1037-3 welcher Rest ?: [ off-topic ]
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:55 Do 11.12.2008
Autor: Loddar

Hallo Al!


> Nach Adam Ries ...

Wie schön: es gibt doch noch Leute, die diesen Namen nur mit einem "e" (und zwar links vom "s"!) schreiben! [daumenhoch]


Gruß
Loddar


PS: natürlich ein großes [respekt] in reverend's Richtung!


Bezug
                                        
Bezug
3^1037-3 welcher Rest ?: auch OT
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:19 Do 11.12.2008
Autor: reverend

@Al, Loddar:
[hut]

PS: Womöglich hat meine Frau doch Recht, dass ich in letzter Zeit viel Zeit in diesem Forum verbringe...

Bezug
                                                
Bezug
3^1037-3 welcher Rest ?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:31 Do 11.12.2008
Autor: angela.h.b.


> PS: Womöglich hat meine Frau doch Recht, dass ich in
> letzter Zeit viel Zeit in diesem Forum verbringe...

Hallo,

sie sollte nicht meinen Mann treffen...

Aber schläfst Du eigentlich auch mal oder ißt? Denn stündlich ein Post ist wirklich viel - und die sind ja oftmals nicht kurz.

Gruß v. Angela


Bezug
                                        
Bezug
3^1037-3 welcher Rest ?: auch off topic
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:26 Do 11.12.2008
Autor: angela.h.b.


> > Nach Adam Ries ...
>  
> Wie schön: es gibt doch noch Leute, die diesen Namen nur
> mit einem "e" (und zwar links vom "s"!) schreiben!
> [daumenhoch]

Hallo,

hier bei uns auf dem Markt habe ich schon mehrfach gehört, daß ich "nach Adams Riese" soundsoviel zu bezahlen habe.

Gruß v. Angela





Bezug
                
Bezug
3^1037-3 welcher Rest ?: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 21:08 Do 11.12.2008
Autor: svcds

wie komm ich denn auf 12 als Rest?! Frag ich mich...

also wenn ich mit den 113 weiterrechne, vielleicht komm ich dann auf das Ergebnis.

Vielen Dank!

Bezug
                        
Bezug
3^1037-3 welcher Rest ?: Antwort
Status: (Antwort) fertig Status 
Datum: 21:43 Do 11.12.2008
Autor: MathePower

Hallo svcds,

> wie komm ich denn auf 12 als Rest?! Frag ich mich...


Das fragen wir uns auch.


>  
> also wenn ich mit den 113 weiterrechne, vielleicht komm ich
> dann auf das Ergebnis.
>  
> Vielen Dank!


Gruß
MathePower

Bezug
                
Bezug
3^1037-3 welcher Rest ?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:40 Do 11.12.2008
Autor: MathePower

Hallo reverend,


> Ich habe zwar alle Posts gelesen, setze aber doch noch
> einmal vorn an.
>  
> Die Aufgabenstellung ist eine klare Übungsaufgabe zum schon
> mehrfach angegebenen "kleinen Fermat", einem recht
> effektiven Primzahltest.
>  
> Ist p eine Primzahl, dann gilt für jede zu p teilerfremde
> Basis a:
>  [mm]a^{p-1}\equiv1\mod{p}[/mm]
>  
> Diese übliche Formulierung des Satzes lässt sich natürlich
> auch anders schreiben:
>  [mm]a^p\equiv a\mod{p}[/mm] oder [mm]a^p-a\equiv0\mod{p}[/mm]
>  
> Die letzte Form hast Du hier vorliegen.
>  
> Bevor ich mal an die Rechnung gehe, eine kurze
> Vorüberlegung und ein paar Informationen. Die zu
> untersuchende Zahl heiße n, geprüft wird nun, ob eine der
> obigen Darstellungen wahr ist, hier also [mm]a^n-a\equiv r\mod{n}[/mm]
> mit a=3, n=1037 und r=0. r ist vergleichsweise einfach zu
> ermitteln.
>  
> Mögliche Ergebnisse:
>  [mm]r\not=0 \Rightarrow n\not\in\IP[/mm]
>  r=0 [mm]\Rightarrow[/mm] keine
> Aussage möglich, weitere Tests nötig
>  
> Es gibt sogenannte
> []Pseudoprimzahlen,
> die den kleinen Fermat zu einer Basis oder sogar mehreren
> Basen bestehen. Links zu Besonderheiten findest Du im
> angegebenen Artikel. Besonders interessant finde ich die
> Carmichael-Zahlen und die starken Pseudoprimzahlen (wg.
> ihrer Anwendung im Miller-Rabin-Test).
>  
> Also ermitteln wir r, ich gehe dabei Deine Rechnung ein
> bisschen entlang. Das wäre einfacher, wenn Du nicht nur
> einen Scan gepostet hättest, weil ich dann einfach hier
> kopieren, markieren und ggf. ändern könnte.
>  Glücklicherweise (für mich) brauchen wir Deine Vorlage
> aber auch gar nicht lange:
>  
> Du stellst fest:
>  > [mm]3^7\equiv12\mod{1037}[/mm]

>  Das ist falsch und der Rest der (sonst im Prinzip richtig
> durchgeführten) Rechnung damit auch.
>  
> [mm]3^7=2187\equiv113\mod{1037}[/mm]
>  
> Zur Vereinfachung der Rechnung suchen wir nun eine Potenz
> mit besonders kleinem Rest (am besten natürlich 1).
>
> Die inzwischen bekannte Zerlegung 17*61 nutzen wir nur
> deswegen nicht, weil sie den Test ja ad absurdum führen
> würde: wozu soll ich eine Zahl mit dem kleinen Fermat
> überprüfen, wenn ich schon weiß, dass sie zusammengesetzt
> ist?
>  
> 113 ist kein so kleiner Rest. Zu Fuß ist man eine Weile
> unterwegs, bis sich endlich etwas findet. Leider ist die
> Freude noch verfrüht:
>  [mm]3^{33}\equiv88\mod{1037}[/mm]
>  [mm]3^{59}\equiv41\mod{1037}[/mm]
>  [mm]3^{62}\equiv70\mod{1037}[/mm]
>  Nur diese drei und natürlich [mm]3^1,3^2,3^3,3^4[/mm] lassen Reste
> unter 100.
>  
> Mit Hilfe eines kleinen Programms lassen sich diese Reste
> schnell berechnen, und es findet sich nach einer weiteren
> Durststrecke endlich das Gewünschte:
>  
> [mm]3^{80}\equiv1\mod{1037}[/mm]
>  
> Daraus folgt auch, dass
> [mm]3^{1040}=\left(3^{80}\right)^{13}\equiv1\mod{1037}[/mm]
>  Man kann schon sicher sagen (und leicht zeigen), dass der
> zu untersuchende Term [mm]3^{1037}-3[/mm] die Bedingung nicht
> erfüllen wird, aber gesucht ist hier ja das genaue
> Ergebnis.
>  
> Einige der bisherigen Ergebnisse sind nützlich, um
> Rechenzeit zu sparen:
>  
> [mm]3^{1037}=3^{80*12+77}=\left(3^{80}\right)^{12}*3^{62+12+3}\equiv1^{12}*3^{62}*3^{12}*3^3\equiv70*113*27\equiv213570\equiv985\mod{1037}[/mm]
>  


Nach dieser Rechnung ist

[mm]3^{12} \ \equiv \ 113 \ \left(1037\right)[/mm]

Dies ist jedoch falsch.



> Nun ist noch die 3 abzuziehen, und insgesamt erhält man:
>  
> [mm]3^{1037}-3\equiv982\mod{1037}[/mm]


Somit lautet das Ergebnis auch nicht

[mm]3^{1037}-3 \ \equiv \ \red{982} \ \left(1037\right)[/mm]


>  
> Ergebnis: 1037 ist nicht prim. :-)
>  


Gruß
MathePower

Bezug
                        
Bezug
3^1037-3 welcher Rest ?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:41 Do 11.12.2008
Autor: reverend

oops.
Klassischer Einsetzungsfehler.
Muss hier grad off, weil mein Taxi fährt, mehr gleich von zuhause (in ca. 30 min).

Bezug
                                
Bezug
3^1037-3 welcher Rest ?: Hochnötige Korrektur!
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 23:46 Do 11.12.2008
Autor: reverend

Hallo MathePower,

ganz herzlichen Dank für den Hinweis. Wenn schon alles dasteht, ist es doch schade, wenn die Rechnung im Finish schiefgeht wie hier bei mir.
Hier also erst einmal das richtige Ergebnis, den anderen Beitrag werde ich gleich angemessen editieren.

***

Hallo svcds,

wie Du siehst, fällt es leicht, sich zu verrechnen. Das war zwar ein kurzer Weg, aber zugleich kein allgemeingültiger. Insofern ein Nachtrag vorab: die Bequemlichkeit kleiner Reste verleitet leicht dazu, lange nach ebensolchen zu suchen. Ganz mechanisch aber führt typischerweise eine Binärdarstellung des Exponenten zum Ziel. [mm] 1037_{10}=10000001101_2, [/mm] das heißt, es genügt [mm] 3^{(2^{10})}*3^{13} [/mm] zu ermitteln, keine schwierige Aufgabe. So würde man normalerweise verfahren.

Vorhin hätte ich meine Exceltabelle einfach weiter ausdehnen sollen; im Büro steht mir außer dem Windowstaschenrechner keine stationäre Rechenhilfe zur Verfügung, aber mehr wäre auch nicht nötig gewesen. Es hätte genügt, die vorliegenden Zwischenergebnisse richtig einzusetzen:

[mm] 3^{62}*\red{3^{12}}*3^3\equiv70*\red{113}*27\equiv\red{213570\equiv985}\mod{1037} [/mm]
Alles rot Markierte ist falsch. [mm] 3^{12} [/mm] war noch gar nicht berechnet, und die eingesetzten 113 waren das Äquivalent von [mm] 3^7. [/mm]

Richtig wäre z.B. folgender Abschluss gewesen:
[mm] 3^{77}=3^{62+7+7+1}=3^{62}*(3^7)^2*3\equiv70*113^2*3\equiv2681490\equiv\blue{845}\mod{1037} [/mm]

Nun ist noch die 3 abzuziehen, und insgesamt erhält man:

[mm] 3^{1037}-3\equiv\blue{842}\mod{1037} [/mm]

Ergebnis: 1037 ist nicht prim. :-)
Na, wenigstens das bleibt. Schade nur, dass wir das ja alle schon vorher wussten...


Bezug
                                        
Bezug
3^1037-3 welcher Rest ?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:57 Fr 12.12.2008
Autor: svcds

habs rausbekommen, waren wohl nur rechenfehler.

vielen vielen dank!

habs jetzt so gemacht http://www.speedshare.org/download.php?id=C031D5E613

Bezug
                                                
Bezug
3^1037-3 welcher Rest ?: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:38 Fr 12.12.2008
Autor: reverend

Das ist aber eine hübsche Lösung - Glückwunsch!

Bezug
                                                        
Bezug
3^1037-3 welcher Rest ?: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:36 Sa 13.12.2008
Autor: svcds

Aufgabe
Kann man an Hand dieses Restes entscheiden, ob 1037 eine Primzahl ist oder nicht?
(Begründung ?)

ähhm wie soll ich denn jetzt die 2. Aufgabe machen?

also ich würd ja schreiben, dass r [mm] \not=0 [/mm] ist und dies durch den kleinen Satz von Fermat begründet ist.

Bezug
                                                                
Bezug
3^1037-3 welcher Rest ?: Antwort
Status: (Antwort) fertig Status 
Datum: 16:33 Sa 13.12.2008
Autor: angela.h.b.


> Kann man an Hand dieses Restes entscheiden, ob 1037 eine
> Primzahl ist oder nicht?
>  (Begründung ?)
>  ähhm wie soll ich denn jetzt die 2. Aufgabe machen?
>  
> also ich würd ja schreiben, dass r [mm]\not=0[/mm] ist und dies
> durch den kleinen Satz von Fermat begründet ist.

Hallo,

dann schreib es!

Gruß v. Angela



Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


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