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 Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

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:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenZahlentheoriemodulo Rechnung
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Zahlentheorie" - modulo Rechnung
modulo Rechnung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

modulo Rechnung: Potenz kongruent zu 1
Status: (Frage) beantwortet Status 
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

        
Bezug
modulo Rechnung: Antwort
Status: (Antwort) fertig Status 
Datum: 22:25 Fr 10.10.2014
Autor: Al-Chwarizmi


> 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]


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


Bezug
                
Bezug
modulo Rechnung: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                        
Bezug
modulo Rechnung: Antwort
Status: (Antwort) fertig Status 
Datum: 14:21 Sa 11.10.2014
Autor: Al-Chwarizmi


> 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.


Bezug
                                
Bezug
modulo Rechnung: Test mit Mathematica
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:34 Sa 11.10.2014
Autor: Al-Chwarizmi

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.



Bezug
                        
Bezug
modulo Rechnung: Antwort
Status: (Antwort) fertig Status 
Datum: 15:45 Sa 11.10.2014
Autor: reverend

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

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


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