Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

ZT: Satz von Fermat-Euler
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> ZT: Satz von Fermat-Euler
 
Autor Nachricht
Tiamat
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 25.01.2008
Beiträge: 2092
Wohnort: Aurich

BeitragVerfasst am: 06 Jan 2009 - 07:31:03    Titel: ZT: Satz von Fermat-Euler

Hallo,

eine simpel erscheinende Aufgabe, die aber doch eine Fußangel hat:

Sei ggT(n,10)=1. Zeigen Sie, dass n^4 ≡ 1 mod 80 ist.

Nun ist 80 = 2^4 * 5, hat also nur die Primteiler 2 und 5. Da n zu 10 teilerfremd ist, ist n weder durch 2 noch durch 5 teilbar, also ist der Satz von Euler anwendbar:

n^(phi(5)) ≡ n^4 ≡ 1 mod 5 und
n^(phi(16)) ≡ n^8 ≡ 1 mod 16

Nun bräuchte ich ja nicht n^8 ≡ 1 mod 16, sondern n^4 ≡ 1 mod 16, um das Ganze zu n^4 ≡ 1 mod 80 zusammenfassen zu können. Wie komme ich da hin? Das Eulerkriterium a^(p-1)/2 ≡ (a/p) mod p fällt aus, da ich mit 16 keine Primzahl habe und 16 und 4 erst recht nicht teilerfremd sind. Wie mache ich es dann?
Calculus
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 02.01.2008
Beiträge: 5077
Wohnort: Bochum

BeitragVerfasst am: 06 Jan 2009 - 16:52:30    Titel:

n ist (mod 80) invertierbar, vielleicht kann man das benutzen?
Annihilator
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 18.05.2007
Beiträge: 6394
Wohnort: (hier nicht mehr aktiv)

BeitragVerfasst am: 06 Jan 2009 - 17:28:54    Titel:

Es lässt sich zeigen, dass (n^4 mod 10 = 1) gilt, woraus auch (n^4 mod 80 = 1) folgt:

Rechnung in Z_10:
n^4 == 1
n^4 - 1 == 0
(n+1) (n-1) (n²+1) == 0

Aus (ggT(n, 10) = 1) folgt (n € {3, 5, 7, 9} + 10Z). Für jedes beliebige n wird mindestens einer dieser Faktoren Null:

> 1. Fall: n = 10k+1
Der zweite Faktor wird betrachtet: n-1 = 10k == 0

> 2. Fall: n = 10k+3
Der dritte Faktor wird betrachtet: n²+1 = 100k² + 60k + 10 == 0

> 3. Fall: n = 10k+7
Der dritte Faktor wird betrachtet: n²+1 = 100k² + 140k + 50 == 0

> 4. Fall: n = 10k+9
Der zweite Faktor wird betrachtet: n+1 = 10(k+1) == 0

Ergo gilt (n^4 mod 10 = 1) für beliebige n oder anders formuliert:

n^4 = 10p+1
n^4 = 10(8q)+1
n^4 = 80q+1
n^4 mod 80 = 1
Calculus
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 02.01.2008
Beiträge: 5077
Wohnort: Bochum

BeitragVerfasst am: 06 Jan 2009 - 17:35:35    Titel:

Und woher weiß man, dass p von der Form 8q ist?
Tiamat
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 25.01.2008
Beiträge: 2092
Wohnort: Aurich

BeitragVerfasst am: 06 Jan 2009 - 17:45:55    Titel:

Das wäre auch mein Einwand...
Erstmal brauchst du die ganzen Fallunterscheidungen ja gar nicht, wenn du den Satz von Euler benutzt, daraus folgt n^4 ≡ 1 mod 10 direkt.

Zweitens kann ich deine Umformungen am Ende nicht ganz nachvollziehen. Ich kann doch nicht von n^4 ≡ 1 mod 10 auf n^4 ≡ 1 mod 80 schließen, das geht doch nur in umgekehrter Richtung, oder?

Ich könnte ja auch mit n^4 ≡ 1 mod 8 anfangen (ebenfalls mit Satz von Euler) und dann auf n^4 ≡ 1 mod 80 schließen, aber das geht z.B. bei 5 nicht:

5^4 ≡ 625 ≡ 1 mod 8, aber 5^4 ≡ 65 mod 80.

Oder liegt es daran, dass 8 noch andere Teiler als nur 2 hat und 10 genau aus den Teilern 2 und 5 besteht?
Annihilator
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 18.05.2007
Beiträge: 6394
Wohnort: (hier nicht mehr aktiv)

BeitragVerfasst am: 06 Jan 2009 - 20:07:16    Titel:

Hmm... Der Beitrag ist in Eile entstanden und eure Kritik ist sehr gerechtfertigt - sorry für diesen Quatsch von oben.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> ZT: Satz von Fermat-Euler
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum