Kongruenz Eulersche Funktion < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Seien m, n [mm] \in \IN [/mm] mit m, n > 1 und ggT(m, n) = 1. Beweisen Sie, dass [mm] m^{\phi(n)} [/mm] + [mm] n^{\phi(m)} \equiv [/mm] 1 (mod mn) ist. |
Hallo,
ich weiß hier leider nicht mehr weiter. Ich denke, man müsste irgendwie zeigen können, dass ggT(mn, [mm] m^{\phi(n)} [/mm] + [mm] n^{\phi(m)}) [/mm] = 1. Aber wie? Oder führt hier ein anderer Weg weiter?
Gruß und Danke,
Martin
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:56 Fr 06.11.2020 | | Autor: | statler |
> Seien m, n [mm]\in \IN[/mm] mit m, n > 1 und ggT(m, n) = 1. Beweisen
> Sie, dass [mm]m^{\phi(n)}[/mm] + [mm]n^{\phi(m)} \equiv[/mm] 1 (mod mn) ist.
Hallo,
>
> ich weiß hier leider nicht mehr weiter. Ich denke, man
> müsste irgendwie zeigen können, dass ggT(mn, [mm]m^{\phi(n)}[/mm]
> + [mm]n^{\phi(m)})[/mm] = 1. Aber wie? Oder führt hier ein anderer
> Weg weiter?
ggT(mn, [mm]m^{\phi(n)}[/mm] + [mm]n^{\phi(m)})[/mm] = 1 ist klar, reicht aber erstmal nicht. Wenn p|m, dann p [mm] $\nmid$ [/mm] n und folglich auch p [mm] $\nmid$ [/mm] ([mm]m^{\phi(n)} + n^{\phi(m)}[/mm])
Die Exponenten spielen also eine Rolle.
Gruß Dieter
|
|
|
| |
|
Hallo,
hast du noch einen weiteren Tipp für mich?
Danke und Gruß,
Martin
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:58 Fr 06.11.2020 | | Autor: | statler |
siehe unten
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:33 Fr 06.11.2020 | | Autor: | statler |
> Seien m, n [mm]\in \IN[/mm] mit m, n > 1 und ggT(m, n) = 1. Beweisen
> Sie, dass [mm]m^{\phi(n)}[/mm] + [mm]n^{\phi(m)} \equiv[/mm] 1 (mod mn) ist.
Nach Lage der Dinge ist jedenfalls
[mm]m^{\phi(n)}[/mm] + [mm]n^{\phi(m)} \equiv[/mm] 0 + 1 [mm] $\equiv$ [/mm] 1 (mod m)
und
[mm]m^{\phi(n)}[/mm] + [mm]n^{\phi(m)} \equiv[/mm] 1 + 0 [mm] $\equiv$ [/mm] 1 (mod n)
Aber dann ist auch
[mm]m^{\phi(n)}[/mm] + [mm]n^{\phi(m)} \equiv[/mm] 1 (mod mn),
da (m, n) = 1.
Gruß Dieter
|
|
|
| |
|
Hallo,
ich muss hier nochmal nerven:
> Aber dann ist auch
> [mm]m^{\phi(n)}[/mm] + [mm]n^{\phi(m)} \equiv[/mm] 1 (mod mn),
> da (m, n) = 1.
Wie kann man das sehen? Welche Regel kommt hier beim letzten Schritt zum Tragen?
Gruß und Danke,
Martin
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:57 Fr 06.11.2020 | | Autor: | statler |
Mahlzeit!
>
> > Aber dann ist auch
> > [mm]m^{\phi(n)}[/mm] + [mm]n^{\phi(m)} \equiv[/mm] 1 (mod mn),
> > da (m, n) = 1.
>
> Wie kann man das sehen? Welche Regel kommt hier beim
> letzten Schritt zum Tragen?
[mm] $m^{\phi(n)} [/mm] + [mm] n^{\phi(m)} [/mm] - 1$ ist durch m und durch n teilbar, dann ist es wegen (m, n) = 1 auch durch das Produkt teilbar. m und n haben verschiedene Primfaktoren!
Jetzt klarer?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:21 Fr 06.11.2020 | | Autor: | sancho1980 |
Ja stimmt...
Das las sich vorhin wie so eine "geläufige" Rechenregel, aber in meinem Skript konnte ich das nirgends finden. Aber wenn ich so drüber nachdenke; halten wir fest:
Sei [mm] {p_{m_1}}^{e_{m_1}} \cdots {p_{m_x}}^{e_{m_x}} [/mm] die kanonische Primfaktorzerlegung von m und [mm] {p_{n_1}}^{e_{n_1}} \cdots {p_{n_y}}^{e_{n_y}} [/mm] die kanonische Primfaktorzerlegung von n. Wegen ggt(m,n) = 1 gilt [mm] ((p_{m_1} \not= p_{n_1}) \land \ldots \land (p_{m_1} \not= p_{n_y})) \land \ldots \land ((p_{m_x} \not= p_{n_1}) \land \ldots \land (p_{m_x} \not= p_{n_y})). [/mm] Dann folgt aus ((m [mm] \vert [/mm] a) [mm] \land [/mm] (n [mm] \vert [/mm] a)) dass ((m [mm] \vert \frac{a}{n}) \land [/mm] (n [mm] \vert \frac{a}{m})) [/mm] und damit auch mn [mm] \vert [/mm] a.
Super, danke!
|
|
|
|
