Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

Beweisaufgabe

ZahlReich - Mathematik Hausaufgabenhilfe » Universitäts-Niveau » Zahlentheorie » Beweisaufgabe « Zurück Vor »

Das Archiv für dieses Kapitel findest Du hier.

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Quirli
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Unregistrierter Gast
Veröffentlicht am Freitag, den 12. November, 2004 - 11:42:   Beitrag drucken

Hallo!
Ich bräuchte Hilfe bei einem Beweis:
Beweisen Sie: Für beliebige natürliche Zahlen a,n>=2 gilt n|phi(a^n-1).

Ich hab leider nicht die geringste Idee, wie ich das angehen soll. Der Prof meinte, dass wir Primitivwurzeln verwenden sollen, damit es einfach(er) wird aber das hilft mir auch nichts.
Vielleicht hat ja von euch jemand eine Idee...

Gruß
Quirli
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Zaph

Nummer des Beitrags: 1749
Registriert: 07-2000
Veröffentlicht am Freitag, den 12. November, 2004 - 13:08:   Beitrag drucken

Das ist ja witzig, und ich dachte zunächst an einen Schreibfehler! Wo doch schon
n | a^phi(n) - 1
gilt. Aber das hier scheint auch zu stimmen. Zumindest fällt mir ad hoc kein Gegenbeispiel ein.
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Quirli
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Unregistrierter Gast
Veröffentlicht am Freitag, den 12. November, 2004 - 17:32:   Beitrag drucken

Das steht schon so auf meinem Blatt. Ich habe nur keine Ahnung, wie ich das beweisen soll. Hast du nicht einen Tipp?
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Gast
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Unregistrierter Gast
Veröffentlicht am Samstag, den 13. November, 2004 - 08:51:   Beitrag drucken

Ist a^n = 1 (mod x) und ggT(a,x)=1
dann gilt nach Lagrange
n | phi(x)

Setze x=a^n - 1
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Quirli
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Unregistrierter Gast
Veröffentlicht am Samstag, den 13. November, 2004 - 10:21:   Beitrag drucken

Hm, aber ich habe doch gar nicht gegeben, dass a^n=1(mod x) und ggT(a,x)=1. Wo nimmst du das jetzt her?
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Zaph (Zaph)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Senior Mitglied
Benutzername: Zaph

Nummer des Beitrags: 1750
Registriert: 07-2000
Veröffentlicht am Sonntag, den 14. November, 2004 - 20:40:   Beitrag drucken

Hm, was der Gast sagt, ist gar nicht so übel!

Es ist ziemlich klar, dass immer
ggT(a,a^n - 1) = 1
gilt.

Trivialerweise gilt außerdem für jedes a und jedes n, dass
a^n = 1 mod (a^n - 1).

Zudem ist n die kleinste Zahl k, die
a^k = 1 mod (a^n - 1)
erfüllt, da a^k < a^n für k < n ist.

Also ist n die Ordnung von a modulo a^n - 1, und damit ein Teiler von phi(a^n - 1).

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.

ad

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page