Teilbarkeit < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:06 Mo 20.10.2014 | | Autor: | capri |
| Aufgabe | Zeigen Sie, dass für alle n [mm] \in \IN [/mm] gilt:
$ 4501770 [mm] \left| n^9^7-n $
Hallo,
als erstes habe ich 4501770 zerlegt in:
$ 4501770 = 2*3*5*7*13*17*97 $
Da $ 4501770 = 2*3*5*7*13*17*97 $ gilt ist die Behauptung gleichbedeutend mit
$ n^9^7 \equiv n \quad mod \quad p $
für $ p = 2,3,5,7,13,17,97 $
wie gehe ich nun die verschiedene Fälle durch?
p = 2, Dies folgt daraus, dass n^9^7 und n entweder beide gerade oder beide ungerade sind.
ist das richtig?
p = 3, ?
bei p=2 war es noch okay (falls es richtig ist) , aber zu den anderen Fällen fällt mir nichts ein.
gibt es auch andere Möglichkeiten es zu zeigen?
LG
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:18 Mo 20.10.2014 | | Autor: | Marcel |
Hallo,
> Zeigen Sie, dass für alle n [mm]\in \IN[/mm] gilt:
>
> [mm]4501770 \left| n^9^7-n[/mm]
> Hallo,
> als erstes habe ich 4501770 zerlegt in:
>
> [mm]4501770 = 2*3*5*7*13*17*97[/mm]
>
> Da [mm]4501770 = 2*3*5*7*13*17*97[/mm] gilt ist die Behauptung
> gleichbedeutend mit
>
> [mm]n^9^7 \equiv n \quad mod \quad p[/mm]
>
> für [mm]p = 2,3,5,7,13,17,97[/mm]
>
> wie gehe ich nun die verschiedene Fälle durch?
>
> p = 2, Dies folgt daraus, dass [mm]n^9^7[/mm] und n entweder beide
> gerade oder beide ungerade sind.
> ist das richtig?
ja, wäre es.
Ich würde mir aber mal folgendes angucken:
[mm] $n^{97}-n=n*(n^{96}-1)=n*(n^{48}+1)*(n^{48}-1)=n*(n^{48}+1)*(n^{24}+1)*(n^{24}-1)$
[/mm]
[mm] $=\ldots=n*(n^{48}+1)*(n^{24}+1)*(n^{12}+1)*(n^{6}+1)*(n^{3}+1)*(n^{3}-1)$
[/mm]
Vielleicht kann man ja mit diesen Faktoren argumentieren...?
Übrigens, wenn man gar keine Idee haben sollte: Im schlimmsten Falle
kann man auch Induktion probieren...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:44 Di 21.10.2014 | | Autor: | capri |
Hallo,
leider verstehe ich nicht warum du es so gemacht hast, kannst du es erläutern?
wenn ich es so machen würde wie ich angefangen habe:
p = 3, falls n [mm] \equiv [/mm] 0 mod 3 gilt trivialerweise $ [mm] n^9^7 \equiv [/mm] $ n mod 3 .
Wir können also $ n [mm] \not \equiv [/mm] $ 0 mod 3 voraussetzen.
p = 7, wie in p=3, ist der Fall n [mm] \equiv [/mm] 0 mod 7 trivial. Für n [mm] \not \equiv [/mm] 0 mod 7 folgt $ [mm] n^9^7 [/mm] $ [mm] \equiv [/mm] mod 7
falls das richtig ist, wie mache ich es in p=5,13,17,97?
LG
|
|
|
| |
|
Hallo capri,
die wesentliche Reduktion der Aufgabe hast Du schon geleistet.
Alles, was Du noch brauchst, ist der "kleine Fermat": Für [mm] p\in\IP [/mm] und [mm] \ggT{(n,p)}=1 [/mm] gilt [mm] n^{p-1}\equiv 1\bmod{p}.
[/mm]
Außerdem gilt dann auch [mm] n^k\equiv n\bmod{p}\quad\gdw\quad n^{k-1}\equiv 1\bmod{p}.
[/mm]
Damit sind alle auftretenden Kongruenzen leicht zu zeigen, da ja für alle auftretenden p gilt: (p-1)|96.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:40 Di 21.10.2014 | | Autor: | capri |
Hallo,
danke erstmal für deine Antwort.
$ [mm] n^{p-1}\equiv 1\bmod{p}. [/mm] $
d.h. bei p = 5 gilt:
$ [mm] n^{4}\equiv 1\bmod{5}. [/mm] $
und das wärst zu p=5? oder muss man noch was ergänzen?
und bei den anderen p´s wäre es genauso. Mir fehlt aber noch warum ist es denn so? :S also ok das ist zwar der kleine Fermat aber zu der Lösung muss ich doch bestimmt noch was aufschreiben oder nicht?
oder reicht das?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:44 Di 21.10.2014 | | Autor: | MacMath |
> Hallo,
> danke erstmal für deine Antwort.
>
> [mm]n^{p-1}\equiv 1\bmod{p}.[/mm]
>
> d.h. bei p = 5 gilt:
>
>
> [mm]n^{4}\equiv 1\bmod{5}.[/mm]
> und das wärst zu p=5? oder muss
> man noch was ergänzen?
Wegen [mm] $n^{4}\equiv 1\bmod{5}$ [/mm] gilt auch
[mm] $n^{96}\equiv 1\bmod{5}$, [/mm] denn [mm] $n^{96}=n^{4^{24}} [/mm]
> und bei den anderen p´s wäre es genauso. Mir fehlt aber
> noch warum ist es denn so? :S also ok das ist zwar der
> kleine Fermat aber zu der Lösung muss ich doch bestimmt
> noch was aufschreiben oder nicht?
> oder reicht das?
Wurde der kleiner Fermat in der Vorlesung behandelt? Dann reicht das.
Gruß
Daniel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:49 Di 21.10.2014 | | Autor: | capri |
Hallo,
ja es wurde behandelt.
Ok danke, aber wie kommst du auf $ [mm] $n^{96}=n^{4^{24}}$ [/mm] $ ?
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:51 Di 21.10.2014 | | Autor: | MacMath |
> Ok danke, aber wie kommst du auf[mm][/mm][mm] n^{96}=n^{4^{24}}[/mm][mm][/mm] ?
>
Mit Potenzgesetzen?
[mm] n^{96}=n^{4*24}=n^{4^{24}}
[/mm]
Viele Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:52 Di 21.10.2014 | | Autor: | MacMath |
Genau darauf bezieht sich auch reverend mit der Aussage
"Damit sind alle auftretenden Kongruenzen leicht zu zeigen, da ja für alle auftretenden p gilt: (p-1)|96. "
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:57 Di 21.10.2014 | | Autor: | capri |
ok, also
für p=5 ist es jetzt erledigt. Für p=13,17,97
dann mache ich es genauso wie bei p=5, und dann bin ich fertig mit der Aufgabe?
Oder muss ich bei den anderen noch etwas ergänzen?
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:03 Di 21.10.2014 | | Autor: | MacMath |
> ok, also
>
> für p=5 ist es jetzt erledigt. Für p=13,17,97
Auch 13-1, 17-1 und 97-1 sind Teiler von 96. Also funktioniert das komplett analog. Für 97 ist das zu zeigende doch ganz exakt der kleine Fermat.
> dann mache ich es genauso wie bei p=5, und dann bin ich
> fertig mit der Aufgabe?
Ja. Jeder Primfaktor ist damit ein Teiler, und alle Primfaktoren kommen nur einfach vor. Das hattest du doch am Anfang schon festgestellt.
> Oder muss ich bei den anderen noch etwas ergänzen?
Nein
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:04 Di 21.10.2014 | | Autor: | capri |
Ok danke :)
|
|
|
|
|
