3^1037-3 welcher Rest ? < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | 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
|
|
| |
|
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 ![[]](/images/popup.gif) Chinesischen Restsatzes lösen.
>
> lg svcds
Gruß
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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.
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | 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
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | 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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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?
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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 :(
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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 :(
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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:)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:28 Mi 10.12.2008 | | Autor: | svcds |
also ich probier das mal aus und meld mich dann nochmal
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | 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
|
|
|
| |
|
> 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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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...
|
|
|
| |
|
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. 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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]](/images/smileys/huepf.gif "[huepf]")
|
|
|
| |
|
> Ich bekomme gerade angezeigt, dass der lange Beitrag eben
> insgesamt mein 1036. Artikel war.
>
> Dann ist dies der 1037.
>
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]](/images/smileys/applaus.gif "[applaus]") Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:19 Do 11.12.2008 | | Autor: | reverend |
@Al, Loddar:
![[hut]](/images/smileys/hut.gif "[hut]")
PS: Womöglich hat meine Frau doch Recht, dass ich in letzter Zeit viel Zeit in diesem Forum verbringe...
|
|
|
| |
|
> 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
|
|
|
| |
|
> > 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]](/images/smileys/daumenhoch.gif "[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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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!
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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).
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:38 Fr 12.12.2008 | | Autor: | reverend |
Das ist aber eine hübsche Lösung - Glückwunsch!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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.
|
|
|
| |
|
> 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
|
|
|
|
![[respekt]](/images/smileys/respekt.gif "[respekt]"){kind=small}
in reverend's Richtung!
