www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

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

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenAnalysis-SonstigesKleiner Satz von Fermat
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Analysis-Sonstiges" - Kleiner Satz von Fermat
Kleiner Satz von Fermat < Sonstiges < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Analysis-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Kleiner Satz von Fermat: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:35 Mo 25.10.2010
Autor: anno

Aufgabe
Berechnen Sie möglichst effizient:

[mm] 2^{167} [/mm] mod 83


Hallo,

hat jemand eine Idee wie ich genau den Satz von Fernat mit der Hand am effizientesten ausrechne?

Also folgendes weß ich:

[mm] a^{p-1} \equiv [/mm] 1 mod p


p = 83
a = 2
[mm] a^{p-1} [/mm] = [mm] 2^{82} [/mm]


Hat da jemand eine Idee wie ich das machen kann?

        
Bezug
Kleiner Satz von Fermat: Antwort
Status: (Antwort) fertig Status 
Datum: 18:41 Mo 25.10.2010
Autor: angela.h.b.


> Berechnen Sie möglichst effizient:
>  
> [mm]2^{167}[/mm] mod 83
>  
> Hallo,
>  
> hat jemand eine Idee wie ich genau den Satz von Fermat mit
> der Hand am effizientesten ausrechne?
>  
> Also folgendes weiß ich:
>  
> [mm]a^{p-1} \equiv[/mm] 1 mod p
>  
>
> p = 83
>  a = 2
>  [mm]a^{p-1}[/mm] = [mm]2^{82}[/mm]
>  
>
> Hat da jemand eine Idee wie ich das machen kann?

Hallo,

es ist
[mm] 2^{167}=2^{2*82+3}. [/mm]

Vielleicht bringt Dich das auf Ideen - Potenzgesetze nicht vergessen!

Gruß v. Angela




Bezug
                
Bezug
Kleiner Satz von Fermat: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:45 Mo 25.10.2010
Autor: anno

Also da müsste ja dann folgendes herauskommen:

[mm] (2^{2})^{82}*2^{3} \gdw 4^{82}*8 [/mm]

Als Rest kommt dann 8 heraus, kann das sein?

Bezug
                        
Bezug
Kleiner Satz von Fermat: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:01 Mo 25.10.2010
Autor: angela.h.b.


> Also da müsste ja dann folgendes herauskommen:
>  
> [mm](2^{2})^{82}*2^{3} \gdw 4^{82}*8[/mm]
>  
> Als Rest kommt dann 8 heraus, kann das sein?

Ja.

Gruß v. Angela


Bezug
                                
Bezug
Kleiner Satz von Fermat: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:10 Mo 25.10.2010
Autor: anno

Aufgabe
Berechnen Sie möglichst effizient:

[mm] 3^{167} [/mm] mod 17

Also ich würde es hier dann wieder so rechnen:


[mm] 3^{167} \gdw 3^{9*17+14} \gdw (3^{9})^{17} [/mm] * [mm] 3^{14} [/mm]


Allerdings kommt mir hier das [mm] 3^{14} [/mm] doch etwas groß vor. Denn der Rest müsste eigentlich ja 11 ergeben und [mm] 3^{14} [/mm] ist ja dann doch schon einiges > 11...

Bezug
                                        
Bezug
Kleiner Satz von Fermat: Antwort
Status: (Antwort) fertig Status 
Datum: 22:18 Mo 25.10.2010
Autor: abakus


> Berechnen Sie möglichst effizient:
>
> [mm]3^{167}[/mm] mod 17

Hallo. es sollte möglich sein, den Rest von [mm] 3^{16} [/mm] mod 17 zu berechnen.
Vielleicht sogar von [mm] 3^{32}, 3^{48}...? [/mm]
Gruß Abakus

>  Also ich würde es hier dann wieder so rechnen:
>  
>
> [mm]3^{167} \gdw 3^{9*17+14} \gdw (3^{9})^{17}[/mm] * [mm]3^{14}[/mm]
>  
>
> Allerdings kommt mir hier das [mm]3^{14}[/mm] doch etwas groß vor.
> Denn der Rest müsste eigentlich ja 11 ergeben und [mm]3^{14}[/mm]
> ist ja dann doch schon einiges > 11...


Bezug
                                                
Bezug
Kleiner Satz von Fermat: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:24 Mo 25.10.2010
Autor: anno

Ich glaube ich hatte da gerade einen Fehler gemacht:

a = 3

p = 17

[mm] a^{p-1} [/mm] = [mm] 3^{17-1} [/mm] = [mm] 3^{16} [/mm]


[mm] 3^{167} [/mm]  = [mm] 3^{10*16+7} [/mm] = [mm] (3^{10})^{16} [/mm] * [mm] 3^{7} [/mm]

Allerdings auch noch etwas groß


edit:

wobei

[mm] 3^{7} [/mm] = 2184 [mm] \Rightarrow [/mm] 2184 mod 17 = 11


Ich weiß jetzt allerdings nicht genau ob das formal so korrekt ist. der Rest stimmt zumindest mal.

Bezug
                                                        
Bezug
Kleiner Satz von Fermat: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:31 Mo 25.10.2010
Autor: abakus


> Ich glaube ich hatte da gerade einen Fehler gemacht:
>  
> a = 3
>  
> p = 17
>  
> [mm]a^{p-1}[/mm] = [mm]3^{17-1}[/mm] = [mm]3^{16}[/mm]
>  
>
> [mm]3^{167}[/mm]  = [mm]3^{10*16+7}[/mm] = [mm](3^{10})^{16}[/mm] * [mm]3^{7}[/mm]
>  
> Allerdings auch noch etwas groß

Gehe schrittweise vor.
[mm] 3^3=27, [/mm]
also [mm] 3^3\equiv [/mm] 10 mod 17.
Daraus folgt [mm] 3^6 \equiv [/mm] 100 [mm] \equiv [/mm] -2 mod 17.
Somit gilt [mm] 3^7 \equiv [/mm] -2*3 [mm] \equiv [/mm] -6 [mm] \equiv [/mm] 11 mod 17.
Gruß Abakus


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Analysis-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]