modulo Rechnung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:32 Fr 10.10.2014 | | Autor: | Ellie123 |
Hallo,
und zwar habe ich zwei Fragen:
1)
ich versuche gerade eine natürliche Zahl n zu finden, so dass
[mm] 3^n \equiv [/mm] 1 (mod 107), bin mir aber nicht sicher ob so eine Zahl überhaupt existiert !? Gibt es vielleicht irgendeinen Satz, der auf diese Fragestellung eine Antwort liefert? Habe bei mir im Skript leider nichts dazu gefunden. Kann mir vielleicht jemand helfen?
2) Um die Zahl n zu finden habe ich angefangen die Potenzen von 3 aufsteigend zu berechnen und dann modulo 107 gerechnet. Dabei bin ich auf folgendes Problem gestossen. Ich habe 3^36 mod 107 =0 erhalten und 3^37 mod 107=64. Aber wenn 3^36 die Form k*107 (für ganze Zahl k) hat, müsste dann nicht auch 3^37 ein Vielfaches von 107 sein? Also, was läuft hier falsch?
Habe ich einen Denkfehler oder habe ich falsch gerechnet.
Achso, gerechnet habe ich mit matlab, indem ich mod(3^36,107) bzw. mod(3^37,107) eingegeben habe.
Viele Grüße
Ellie
|
|
| |
|
> Hallo,
>
> und zwar habe ich zwei Fragen:
>
> 1)
> ich versuche gerade eine natürliche Zahl n zu finden, so
> dass
> [mm]3^n \equiv[/mm] 1 (mod 107), bin mir aber nicht sicher ob so
> eine Zahl überhaupt existiert !? Gibt es vielleicht
> irgendeinen Satz, der auf diese Fragestellung eine Antwort
> liefert? Habe bei mir im Skript leider nichts dazu
> gefunden. Kann mir vielleicht jemand helfen?
>
> 2) Um die Zahl n zu finden habe ich angefangen die Potenzen
> von 3 aufsteigend zu berechnen und dann modulo 107
> gerechnet. Dabei bin ich auf folgendes Problem gestossen.
> Ich habe 3^36 mod 107 =0 erhalten ![[haee]](/images/smileys/haee.gif "[haee]")
Dies kann natürlich auf keinen Fall stimmen, denn falls es
zuträfe, könnte man daraus schließen, dass 107 durch 3
teilbar sein müsste, was aber offensichtlich nicht der Fall ist.
> und 3^37 mod 107=64.
> Aber wenn 3^36 die Form k*107 (für ganze Zahl k) hat,
> müsste dann nicht auch 3^37 ein Vielfaches von 107 sein?
> Also, was läuft hier falsch?
> Habe ich einen Denkfehler oder habe ich falsch gerechnet.
> Achso, gerechnet habe ich mit matlab, indem ich
> mod(3^36,107) bzw. mod(3^37,107) eingegeben habe.
Na, dass du mit Matlab gerechnet hast, ist der entscheidende
Hinweis darauf, wo der Fehler liegt.
Matlab rechnet nicht mit beliebig großen Zahlen exakt. Offenbar
bist du über die Grenze hinaus gekommen, wo man exakte
Resultate erwarten kann. Da kannst du also auf die Ergebnisse
einfach nicht mehr vertrauen. Eigentlich wäre es schön, wenn
Matlab selber einen Hinweis auf mögliche Fehlerquellen gäbe,
wenn man die Modulo-Funktion in einem Bereich anwenden
will, wo dies gar nicht mehr klappen kann.
Die Aufgabe ist bestimmt auch nicht so gedacht, dass man sie
durch reines Suchen mittels Rechner lösen kann.
Als Tipp möchte ich dir nur diese Frage stellen: hast du
schon irgendwo (vielleicht in der Vorlesung) vom "kleinen
Fermat" gehört ?
LG , Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:30 Sa 11.10.2014 | | Autor: | Ellie123 |
Hallo,
danke für die Antwort.
>
> Dies kann natürlich auf keinen Fall stimmen, denn falls
> es
> zuträfe, könnte man daraus schließen, dass 107 durch 3
> teilbar sein müsste, was aber offensichtlich nicht der
> Fall ist.
> Na, dass du mit Matlab gerechnet hast, ist der
> entscheidende
> Hinweis darauf, wo der Fehler liegt.
> Matlab rechnet nicht mit beliebig großen Zahlen exakt.
> Offenbar
> bist du über die Grenze hinaus gekommen, wo man exakte
> Resultate erwarten kann. Da kannst du also auf die
> Ergebnisse
> einfach nicht mehr vertrauen. Eigentlich wäre es schön,
> wenn
> Matlab selber einen Hinweis auf mögliche Fehlerquellen
> gäbe,
> wenn man die Modulo-Funktion in einem Bereich anwenden
> will, wo dies gar nicht mehr klappen kann.
Habe jetzt mit Mupad gerechnet und mod(3^36,107)=90 und mod(3^36,107)=56 erhalten. Ich glaube doch, dass Mupad exakt rechnet?!
Damit hat sich die erste Frage ja erledigt.
>
> Die Aufgabe ist bestimmt auch nicht so gedacht, dass man
> sie
> durch reines Suchen mittels Rechner lösen kann.
>
> Als Tipp möchte ich dir nur diese Frage stellen: hast du
> schon irgendwo (vielleicht in der Vorlesung) vom "kleinen
> Fermat" gehört ?
Ja, ich hatte schon mal von diesem Satz gehört, hatte ihn aber nicht mehr so ganz parat. Ich habe nochmal gegoogelt und jetzt rausgefunden, dass eine häufig benutzte Form die folgende ist: Für eine Primzahl p und eine ganze Zahl a, die kein Vielfaches von p ist, gilt die folgende Kongruenz:
[mm] a^{p-1} \equiv [/mm] 1 (mod p)
Nach diesem Satz würde gelten:
[mm] \[3^{106}\] \equiv [/mm] 1 (mod 107)
Allerdings habe ich noch folgendes Problem. Was ich nicht dazu geschrieben habe ist, dass ich die kleinstmögliche Zahl n suche für die
[mm] 3^n \equiv [/mm] 1 (mod 107) gilt. Und darüber sagt der Satz ja wohl nichts aus, oder?
Wie kann ich also die kleinstmögliche Zahl n mit dieser Eigenschaft finden?
Viele Grüße
Ellie
|
|
|
| |
|
> Hallo,
>
> danke für die Antwort.
>
> >
> > Dies kann natürlich auf keinen Fall stimmen, denn falls
> > es
> > zuträfe, könnte man daraus schließen, dass 107 durch
> 3
> > teilbar sein müsste, was aber offensichtlich nicht der
> > Fall ist.
> > Na, dass du mit Matlab gerechnet hast, ist der
> > entscheidende
> > Hinweis darauf, wo der Fehler liegt.
> > Matlab rechnet nicht mit beliebig großen Zahlen exakt.
> > Offenbar
> > bist du über die Grenze hinaus gekommen, wo man
> exakte
> > Resultate erwarten kann. Da kannst du also auf die
> > Ergebnisse
> > einfach nicht mehr vertrauen. Eigentlich wäre es
> schön,
> > wenn
> > Matlab selber einen Hinweis auf mögliche Fehlerquellen
> > gäbe,
> > wenn man die Modulo-Funktion in einem Bereich anwenden
> > will, wo dies gar nicht mehr klappen kann.
>
> Habe jetzt mit Mupad gerechnet und mod(3^36,107)=90 und
> mod(3^36,107)=56 erhalten. Ich glaube doch, dass Mupad
> exakt rechnet?!
Bei Mupad kenne ich mich nicht so recht aus. Ich arbeite
hie und da mit Mathematica, und damit sollte es jedenfalls
klappen.
> Damit hat sich die erste Frage ja erledigt.
>
> >
> > Die Aufgabe ist bestimmt auch nicht so gedacht, dass man
> > sie
> > durch reines Suchen mittels Rechner lösen kann.
> >
> > Als Tipp möchte ich dir nur diese Frage stellen: hast du
> > schon irgendwo (vielleicht in der Vorlesung) vom
> "kleinen
> > Fermat" gehört ?
>
> Ja, ich hatte schon mal von diesem Satz gehört, hatte ihn
> aber nicht mehr so ganz parat. Ich habe nochmal gegoogelt
> und jetzt rausgefunden, dass eine häufig benutzte Form die
> folgende ist: Für eine Primzahl p und eine ganze Zahl a,
> die kein Vielfaches von p ist, gilt die folgende
> Kongruenz:
>
> [mm]a^{p-1} \equiv[/mm] 1 (mod p)
>
> Nach diesem Satz würde gelten:
> [mm]\[3^{106}\] \equiv[/mm] 1 (mod 107)
> Allerdings habe ich noch folgendes Problem. Was ich nicht
> dazu geschrieben habe ist, dass ich die kleinstmögliche
> Zahl n suche für die
> [mm]3^n \equiv[/mm] 1 (mod 107) gilt. Und darüber sagt der Satz ja
> wohl nichts aus, oder?
> Wie kann ich also die kleinstmögliche Zahl n mit dieser
> Eigenschaft finden?
>
> Viele Grüße
> Ellie
Hallo Ellie,
zumindest haben wir aber mit n=106 mal eine (nicht allzu
riesige) obere Schranke für das gesuchte kleinste n.
Nun kann man sich weiter überlegen, dass wohl auch
schon n=53 genügt, wegen $\ [mm] 3^{106}\ [/mm] =\ [mm] \left(3^{53}\right)^2$ [/mm] .
Eine Begründung überlasse ich dir.
Mit WolframAlpha (das auf Mathematica basiert), habe
ich dies getestet.
Um ganz sicher zu sein, ob man mit n=53 wirklich das
kleinstmögliche n hat, könnte man nun allenfalls halt auch
wieder mit Mupad oder Wolfram nachrechnen, ob man
noch ein kleineres n finden kann, woran ich aber sehr
zweifle.
LG , Al-Chw.
|
|
|
| |
|
Hallo Ellie,
ich hab's gerade mal mit Mathematica getestet.
Eingabezeile:
Table [Mod [3^n ,107 ], {n,1,53 }]
Ausgabe:
{3, 9, 27, 81, 29, 87, 47, 34, 102, 92, 62, 79, 23, 69, 100, 86, 44, 25, 75, [mm] \
[/mm]
11, 33, 99, 83, 35, 105, 101, 89, 53, 52, 49, 40, 13, 39, 10, 30, 90, 56, 61, [mm] \
[/mm]
76, 14, 42, 19, 57, 64, 85, 41, 16, 48, 37, 4, 12, 36, 1}
Du siehst: Die 1 kommt wirklich erst an der letzten (53.)
Stelle !
LG , Al-Chw.
|
|
|
| |
|
Hallo Ellie,
da [mm] \ggT{(3,107)}=1 [/mm] ist, gilt nicht nur der "kleine Fermat".
Wir wissen [mm] 3^{106}\equiv 1\bmod{107}.
[/mm]
Wenn es nun ein kleineres $k$ mit [mm] 3^k\equiv 1\bmod{107} [/mm] gibt, dann muss $k|106$ gelten. Damit kommen also nur [mm] k\in\{1,2,53\} [/mm] als kleinere in Frage. Die ersten beiden sind leicht auszuschließen, $k=53$ muss man prüfen. Das hat Al ja schon erledigt.
Sogar das könnte man sich hier noch sparen, wenn man wüsste, ob 3 ein quadratischer Rest [mm] \bmod{107} [/mm] ist. Wenn ja, dann ist [mm] 3^{53}\equiv 1\bmod{107}. [/mm] Siehst Du, warum?
Das hilft aber auch nur, wenn man z.B. [mm] 18^2=324\equiv 3\bmod{107} [/mm] schnell erkennt.
Grüße
reverend
|
|
|
|
