Satz von Euler < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo Leute,
ich glaube ich steh' momentan ein bisschen auf der Leitung. Es geht um den Satz von Euler:
[mm] \ggT(a, [/mm] m) = 1 [mm] \Rightarrow a^{\varphi(m)} \equiv [/mm] 1 [mm] \pmod [/mm] m
So weit ist alles klar, auch den Beweis für diesen Satz verstehe ich. Aber warum - und vor allem wie - folgt daraus
[mm] a^n \equiv a^{n'} \pmod{m}, [/mm] falls n [mm] \equiv [/mm] n' [mm] \pmod{\varphi(m)} [/mm]
Konkret geht es darum, dass ich zeigen muss, dass für ein zu 3 teilerfremdes a folgendes gilt:
wenn b [mm] \equiv [/mm] c [mm] \pmod{6}, [/mm] so gilt [mm] a^b \equiv a^c \pmod{9}
[/mm]
Ich wäre sehr dankbar für eine Hilfestellung!
Liebe Grüße,
Wolfram
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo Wolfram,
aus [mm] $n\equiv [/mm] n' [mm] \mod \varphi(m)$ [/mm] folgt, dass n und n' den gleichen Rest mod [mm] $\varphi [/mm] (m)$ haben. Aus [mm] $a^{k \varphi (m)} \equiv (a^{\varphi (m)})^k\equiv [/mm] 1 [mm] \mod [/mm] m$ folgt, dass es nur auf diesen Rest ankommt.
P.S.
> Es geht um den Satz von Euler:
> $ [mm] a^{\varphi(m)} \equiv [/mm] $ 1 $ [mm] \pmod [/mm] $ m
bitte immer mit der Bedingung a teilerfremd zu m. (du erwähnst es ja später). Sonst gilt die Aussage nicht.
|
|
|
| |
|
Danke für die rasche Antwort!
Mir fehlt da irgendwie noch der Bezug zum Modul m. Das n und n' kongruent bezüglich [mm] \varphi(m) [/mm] sind leuchtet mir ein, aber das bedeutet doch nicht, dass n oder n' den Wert von [mm] \varphi(m) [/mm] annehmen müssen, oder? Damit wäre dann [mm] a^n [/mm] nicht mehr kongruent zu 1 mod m.
Übersehe ich da etwas oder habe ich es schlichtweg noch nicht richtig verstanden?
|
|
|
| |
|
Du machst es dir zu schwer.
>
> Mir fehlt da irgendwie noch der Bezug zum Modul m. Das n
> und n' kongruent bezüglich [mm]\varphi(m)[/mm] sind leuchtet mir
Das ist die Voraussetzung. Die finde ich persönlich selten einleuchtend.
> ein, aber das bedeutet doch nicht, dass n oder n' den Wert
> von [mm]\varphi(m)[/mm] annehmen müssen, oder? Damit wäre dann [mm]a^n[/mm]
> nicht mehr kongruent zu 1 mod m.
Müssen sie ja nicht sein.
Nimm mal meine Rechnung aus der ersten Antwort und berechne:
[mm] $a^{k \varphi (m) +l} \mod [/mm] m$.
Sie haben den gleichen Rest und nur das ist bedeutend.
> Übersehe ich da etwas oder habe ich es schlichtweg noch
> nicht richtig verstanden?
|
|
|
| |
|
Ach du meine Güte, vielleicht hätte ich gleich anfangs konkrete Zahlenwerte einsetzen sollen, dann hätte ich mir nicht so lange den Kopf darüber zerbrechen müssen :)
Danke für deine Hilfe!
LG,
Wolfram
|
|
|
|
