Teilbarkeit durch 2730 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:01 Di 07.02.2012 | | Autor: | briddi |
| Aufgabe | | Zeige 2730 teilt [mm] n^{13}-n [/mm] für alle n [mm] \in \IN [/mm] |
Hallo, ich bin gerade am Üben für meine Klausur und habe diese Aufgabe gefunden, bei der ich den Lösungsansatz überhaupt nicht verstehe. Kann mir da jemand auf die Sprünge helfen? Ist vermutlich gar nicht so schwer, ich seh es nur gerade nicht.
Lösungshinweis: [mm] 2730=2*3*5*7*13 [/mm] und 1,2,4,6,12 sind Teiler von [mm] \varphi(13)=12 [/mm]
Ich seh das beides ein, aber inwiefern hilft mir das bei der Lösung der Aufgabe?
Vielen Dank,
briddi
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:30 Di 07.02.2012 | | Autor: | felixf |
Moin briddi!
> Zeige 2730 teilt [mm]n^{13}-n[/mm] für alle n [mm]\in \IN[/mm]
>
> Hallo, ich
> bin gerade am Üben für meine Klausur und habe diese
> Aufgabe gefunden, bei der ich den Lösungsansatz überhaupt
> nicht verstehe. Kann mir da jemand auf die Sprünge helfen?
> Ist vermutlich gar nicht so schwer, ich seh es nur gerade
> nicht.
> Lösungshinweis: [mm]2730=2*3*5*7*13[/mm] und 1,2,4,6,12 sind
> Teiler von [mm]\varphi(13)=12[/mm]
> Ich seh das beides ein, aber inwiefern hilft mir das bei
> der Lösung der Aufgabe?
Kennst du den chinesischen Restsatz und den Satz von Euler bzw. den kleinen Satz von Fermat?
Wenn du das mit deinen Beobachtungen oben kombinierst bist du schnell fertig.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:42 Di 07.02.2012 | | Autor: | briddi |
Ja, kenn ich.
Ich hab das auch schon eben zerlegt: Wenn n nicht teilerfremd ist zu den Primzahlen, ist es offensichtlich. Sei also n nicht Vielfaches von den Moduln, dann kann ich den Satz von Fermat anwenden.
[mm] n^{13}-n\equiv [/mm] 0 (13) gilt, weil [mm] n^{12}*n-n\equiv [/mm] n-n [mm] \equiv [/mm] 0 (13)
[mm] n^{13}-n\equiv [/mm] 0 (2) gilt, weil [mm] n\equiv [/mm] 1 (2)
[mm] n^{13}-n\equiv [/mm] 0 (3) gilt, weil [mm] (n^2){^6}*n-n\equiv [/mm] 0 (3)
[mm] n^{13}-n\equiv [/mm] 0 (5) gilt, weil [mm] (n^4)^3*n-n\equiv [/mm] 0 (5)
[mm] n^{13}-n\equiv [/mm] 0 (7) gilt, weil [mm] (n^6)^2*n-n\equiv [/mm] 0 (7)
Stimmt das so?
Ich benutze dann aber nie, dass 1,2,4,6 und 12 Teiler von [mm] \varphi(13)=12 [/mm] sind. Kann man das vielleicht benutzen um schneller zu einer Lösung zu kommen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:24 Sa 11.02.2012 | | Autor: | felixf |
Moin!
> Ich hab das auch schon eben zerlegt: Wenn n nicht
> teilerfremd ist zu den Primzahlen, ist es offensichtlich.
> Sei also n nicht Vielfaches von den Moduln, dann kann ich
> den Satz von Fermat anwenden.
Du musst das ganze allerdings auch dann beweisen, wenn n nicht teilerfremd zu den Primzahlen ist.
> [mm]n^{13}-n\equiv[/mm] 0 (13) gilt, weil [mm]n^{12}*n-n\equiv[/mm] n-n
> [mm]\equiv[/mm] 0 (13)
> [mm]n^{13}-n\equiv[/mm] 0 (2) gilt, weil [mm]n\equiv[/mm] 1 (2)
> [mm]n^{13}-n\equiv[/mm] 0 (3) gilt, weil [mm](n^2){^6}*n-n\equiv[/mm] 0 (3)
> [mm]n^{13}-n\equiv[/mm] 0 (5) gilt, weil [mm](n^4)^3*n-n\equiv[/mm] 0 (5)
> [mm]n^{13}-n\equiv[/mm] 0 (7) gilt, weil [mm](n^6)^2*n-n\equiv[/mm] 0 (7)
>
> Stimmt das so?
Ja. Aber nur, wenn $n$ wirklich zu allen dieser Primzahlen teilerfremd ist.
> Ich benutze dann aber nie, dass 1,2,4,6 und 12 Teiler von
> [mm]\varphi(13)=12[/mm] sind. Kann man das vielleicht benutzen um
> schneller zu einer Lösung zu kommen?
Nun, ist $p$ ein Primteiler von $2730$, so ist [mm] $\varphi(p) [/mm] = p - 1$ ein Teiler von [mm] $\varphi(13)$, [/mm] wie du bemerkt hast. Also gilt mit Fermat [mm] $n^{\varphi(p)} \equiv [/mm] 1 [mm] \pmod{p}$, [/mm] und somit auch [mm] $n^{\varphi(13)} [/mm] = [mm] n^{12} \equiv [/mm] 1 [mm] \pmod{p}$. [/mm] Und daraus folgt [mm] $n^{12+1} \equiv [/mm] n [mm] \pmod{p}$.
[/mm]
Damit musst du nicht jedes $p$ einzelnd diskutieren.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:43 Mo 04.06.2012 | | Autor: | quasimo |
Hallo felixf,
Ich habe eine Frage, du verwendest in deinem Beweis $ [mm] n^{\varphi(p)} \equiv [/mm] 1 [mm] \pmod{p} [/mm] $
da gilt doch nur wenn ggT(p,n)=1
also ist es in dem Bsp. : $ [mm] n^{\varphi(13)} \equiv [/mm] 1 [mm] \pmod{13} [/mm] $
und nicht p im Modulo?
außerdem kann ich den satz doch nur anwenden ggT(13,n)=1
was mache ich wenn n ein vielfaches von 13 ist?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:54 Di 05.06.2012 | | Autor: | felixf |
Moin,
> Ich habe eine Frage, du verwendest in deinem Beweis
> [mm]n^{\varphi(p)} \equiv 1 \pmod{p}[/mm]
> da gilt doch nur wenn
> ggT(p,n)=1
genau. Ich bezog mich auf diesen Fall.
Im Fall $p [mm] \mid [/mm] n$ muss man anders vorgehen.
> also ist es in dem Bsp. : [mm]n^{\varphi(13)} \equiv 1 \pmod{13}[/mm]
>
> und nicht p im Modulo?
Was meinst du damit?
> außerdem kann ich den satz doch nur anwenden ggT(13,n)=1
> was mache ich wenn n ein vielfaches von 13 ist?
Dann gilt $n [mm] \equiv [/mm] 0 [mm] \pmod{13}$. [/mm] Und [mm] $0^{13}$ [/mm] ist gleich [mm] $0^1$. [/mm] Also gilt auch dann [mm] $n^{13} \equiv [/mm] n [mm] \pmod{13}$.
[/mm]
LG Felix
|
|
|
|
