kleiner Satz von Fermat < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | 1. Zeigen Sie mit Hilfe des kleinen Satzes von Fermat, dass 9 keine Primzahl ist.
2. Berechnen Sie [mm] 1764^{2013} [/mm] mod 2011. |
1.
Der Satz lautet ja:
Sei p eine Primzahl. Für jede Zahl x, die teilerfremd zu p ist gilt:
[mm] x^{p-1} [/mm] = 1 (mod p)
D.h. ich schaue mir die Liste aller teilerfremden Zahlen von 9 an: 1, 2, 4, 5, 7, 8 und fange an zu rechnen:
[mm] 1^{8} [/mm] = 1 (mod 9)
[mm] 2^{8} [/mm] = 4 (mod 9), denn 28 * 9 = 252, 4 dazu addiert, gibt [mm] 2^{8} [/mm]
Somit habe ich gezeigt, dass 9 keine Primzahl ist.
Stimmt das so?
2. Hierfür bräuchte ich mal ein paar Stichwörter wie ich das gelöst bekomme.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:32 Fr 04.09.2009 | | Autor: | zetamy |
Hallo,
> 1. Zeigen Sie mit Hilfe des kleinen Satzes von Fermat, dass
> 9 keine Primzahl ist.
>
> 2. Berechnen Sie [mm]1764^{2013}[/mm] mod 2011.
> 1.
> Der Satz lautet ja:
> Sei p eine Primzahl. Für jede Zahl x, die teilerfremd zu
> p ist gilt:
> [mm]x^{p-1}[/mm] = 1 (mod p)
>
> D.h. ich schaue mir die Liste aller teilerfremden Zahlen
> von 9 an: 1, 2, 4, 5, 7, 8 und fange an zu rechnen:
>
> [mm]1^{8}[/mm] = 1 (mod 9)
> [mm]2^{8}[/mm] = 4 (mod 9), denn 28 * 9 = 252, 4 dazu addiert, gibt
> [mm]2^{8}[/mm]
> Somit habe ich gezeigt, dass 9 keine Primzahl ist.
>
> Stimmt das so?
Siehe Felix unten.
> 2. Hierfür bräuchte ich mal ein paar Stichwörter wie ich
> das gelöst bekomme.
2011 ist eine Primzahl, also gilt nach dem kleinen Satz von Fermat [mm] $1764^{2011-1} [/mm] = [mm] 1764^{2010}=1 \mod [/mm] 2011$. Damit und mit den Potenzgesetzen lässt sich [mm] $1764^{2013}$ [/mm] berechnen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:47 Fr 04.09.2009 | | Autor: | felixf |
Hallo!
> 1. Zeigen Sie mit Hilfe des kleinen Satzes von Fermat, dass
> 9 keine Primzahl ist.
>
> 1.
> Der Satz lautet ja:
> Sei p eine Primzahl. Für jede Zahl x, die teilerfremd zu
> p ist gilt:
> [mm]x^{p-1}[/mm] = 1 (mod p)
>
> D.h. ich schaue mir die Liste aller teilerfremden Zahlen
> von 9 an: 1, 2, 4, 5, 7, 8 und fange an zu rechnen:
Hier benutzt du doch schon, dass $9$ keine Primzahl ist. Wenn 9 eine Primzahl waer, dann waer jede Zahl in [mm] $\{ 1, 2, 3, \dots, 8 \}$ [/mm] teilerfremd zu 9, und du koenntest z.B. auch 3 nehmen. Und [mm] $3^8$ [/mm] ist ganz sicher durch 9 teilbar, womit [mm] $3^8 \equiv [/mm] 0 [mm] \not\equiv [/mm] 1 [mm] \pmod{9}$ [/mm] ist. Da braucht man nichtmals wirklich rechnen, was [mm] $3^8$ [/mm] eigentlich ist :)
LG Felix
|
|
|
|
