Modulo: n^61=n mod 385 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:25 Fr 28.10.2011 | | Autor: | ThomasTT |
| Aufgabe | | Zeigen Sie, dass gilt: [mm] $n^{61}\ \equiv n\quad [/mm] mod\ [mm] 385\quad \forall n\in\IN$ [/mm] |
He,
ich versuche mich derzeit an dieser Aufgabe, aber komme nicht wirklich weiter. Da 385 ja keine Primzahl ist, fallen ja leider viele Theoreme weg, die man anwenden könnten. Mein bester Versuch ist bisher folgender mit dem Satz von Euler.
Es ist [mm] $\varphi(385)=240=4\cdot [/mm] 60$. Damit erhalten wir [mm] $(n^{60})^4 \equiv 1\quad [/mm] mod\ 385$. Ich bin mir jetzt aber unsicher ob gilt:
[mm] $(n^{60})^4 \equiv 1\quad [/mm] mod\ [mm] 385\quad \gdw\quad n^{60} \equiv 1\quad [/mm] mod\ [mm] 385\quad \gdw\quad n^{61} \equiv n\quad [/mm] mod\ 385$
Und falls das gilt, dann hätte ich die Aufgabe auch nur für alle [mm] $n\in\IN$ [/mm] mit $ggT(n,385)=1$ gezeigt. Kann mir jemand vielleicht einen Tipp geben?
Gruß
|
|
| |
|
> Zeigen Sie, dass gilt: [mm]n^{61}\ \equiv n\quad mod\ 385\quad \forall n\in\IN[/mm]
>
Die Beweisidee ist wohl, dass nach dem Fermatschen Satz gilt
[mm] n^{61} [/mm] = n mod p für alle [mm] n\in [/mm] N und [mm] p\in\{5,7,11\},
[/mm]
da 60 jeweils ein Vielfaches von p-1 ist.
Nach dem chinesischen Restsatz ist dann [mm] n^{61} [/mm] = n mod 385
> He,
>
> ich versuche mich derzeit an dieser Aufgabe, aber komme
> nicht wirklich weiter. Da 385 ja keine Primzahl ist, fallen
> ja leider viele Theoreme weg, die man anwenden könnten.
> Mein bester Versuch ist bisher folgender mit dem Satz von
> Euler.
>
> Es ist [mm]\varphi(385)=240=4\cdot 60[/mm]. Damit erhalten wir
> [mm](n^{60})^4 \equiv 1\quad mod\ 385[/mm]. Ich bin mir jetzt aber
> unsicher ob gilt:
> [mm](n^{60})^4 \equiv 1\quad mod\ 385\quad \gdw\quad n^{60} \equiv 1\quad mod\ 385\quad \gdw\quad n^{61} \equiv n\quad mod\ 385[/mm]
>
> Und falls das gilt, dann hätte ich die Aufgabe auch nur
> für alle [mm]n\in\IN[/mm] mit [mm]ggT(n,385)=1[/mm] gezeigt. Kann mir jemand
> vielleicht einen Tipp geben?
>
> Gruß
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:46 Sa 29.10.2011 | | Autor: | ThomasTT |
Ok, danke. Das hat mir den richtigen Faden aufgezeigt.
|
|
|
|
