| Autor |
Beitrag |
    
Quirli
Unregistrierter Gast
| | Veröffentlicht am Freitag, den 12. November, 2004 - 11:42: | 
|
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 |
Zaph (Zaph)
Senior Mitglied
Benutzername: Zaph
Nummer des Beitrags: 1749
Registriert: 07-2000
| | Veröffentlicht am Freitag, den 12. November, 2004 - 13:08: |
|
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. |
Quirli
Unregistrierter Gast
| | Veröffentlicht am Freitag, den 12. November, 2004 - 17:32: |
|
Das steht schon so auf meinem Blatt. Ich habe nur keine Ahnung, wie ich das beweisen soll. Hast du nicht einen Tipp? |
Gast
Unregistrierter Gast
| | Veröffentlicht am Samstag, den 13. November, 2004 - 08:51: |
|
Ist a^n = 1 (mod x) und ggT(a,x)=1
dann gilt nach Lagrange
n | phi(x)
Setze x=a^n - 1 |
Quirli
Unregistrierter Gast
| | Veröffentlicht am Samstag, den 13. November, 2004 - 10:21: |
|
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? |
Zaph (Zaph)
Senior Mitglied
Benutzername: Zaph
Nummer des Beitrags: 1750
Registriert: 07-2000
| | Veröffentlicht am Sonntag, den 14. November, 2004 - 20:40: |
|
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). |
