Primitivwurzeln Äquivalenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:21 Mo 26.05.2014 | | Autor: | huberT |
| Aufgabe | Es sei p eine Primzahl.
Beweise, dass n genau dann eine Primzahl ist, wenn für beliebige b mod n
(X + [mm] b)^n \equiv [/mm] [mm] X^n [/mm] + [mm] b^n [/mm] mod n. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich soll oben genannte Äquivalenz zeigen.
Ich habe mittels des binomischen Lehrsatzes schon gezeigt, dass für beliebige a, b mod p
(a + [mm] b)^p \equiv a^p [/mm] + [mm] b^p [/mm] mod p gilt.
Aber wie hilft mir das weiter um die Äquivalenz zu zeigen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:51 Mo 26.05.2014 | | Autor: | felixf |
Moin!
> Beweise, dass n genau dann eine Primzahl ist, wenn für
> beliebige b mod n
> (X + [mm]b)^n \equiv[/mm] [mm]X^n[/mm] + [mm]b^n[/mm] mod n.
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
> Ich soll oben genannte Äquivalenz zeigen.
> Ich habe mittels des binomischen Lehrsatzes schon gezeigt,
> dass für beliebige a, b mod p
>
> (a + [mm]b)^p \equiv a^p[/mm] + [mm]b^p[/mm] mod p gilt.
>
> Aber wie hilft mir das weiter um die Äquivalenz zu
> zeigen?
Das zeigt vor allem schonmal die eine Richtung.
Du musst jetzt die andere Richtung zeigen: ist $n$ nicht prim, so gibt es $a, b$ mit $(a + [mm] b)^n \not\equiv a^n [/mm] + [mm] b^n \pmod{n}$. [/mm] Untersuche doch erstmal die Faelle $n = p [mm] \cdot [/mm] q$ mit zwei verschiedenen Primzahlen $p$ und $q$, und den Fall $n = [mm] p^2$ [/mm] mit $p$ einer Primzahl. Probiere ein paar einfache Fälle durch, vielleicht fällt dir etwas auf?
LG Felix
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 23:00 Mo 26.05.2014 | | Autor: | huberT |
ich hab das ganze mal ausprobiert:
wenn n = 2 * 3 , dann gilt
(x + [mm] b)^{6} [/mm] = [mm] x^{6} [/mm] + 6*() + 15*() + 20*() + 15*() + 6*() + [mm] b^{6}
[/mm]
[mm] \equiv x^{6} [/mm] + 15*() + 20*() + 15*() + [mm] b^{6} [/mm] mod 6
wobei 2|20 und 3|15.
wenn n = 2*5 , dann gilt
(x + [mm] b)^{10} [/mm] = [mm] x^{10} [/mm] + ... + [mm] b^{10}
[/mm]
[mm] \equiv x^{10} [/mm] + 45*() + 252*() + 45*() + [mm] b^{10} [/mm] mod 10
wobei 2|252 und 5|45.
wenn wir n quadratisch wählen passiert folgendes:
sei n = 2*2, dann gilt
(X + [mm] b)^{4} \equiv x^{4} [/mm] + 6*() + [mm] b^{4} [/mm] mod 4
wobei 2|6.
sei n = 3*3, dann gilt
(x + [mm] b)^{9} \equiv x^{9} [/mm] + 84*( () + () ) + [mm] b^{9} [/mm] mod 9
wobei 3|84.
Es fällt also auf dass die Terme:
15*() + 20*() + 15*()
45*() + 252*() + 45*()
6*()
84*( () + () )
nur von Primzahlen geteilt werden können.
Wie komme ich hier weiter, ich bräuchte noch einen kleinen Denkanstoß.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:07 Di 27.05.2014 | | Autor: | huberT |
Als Lösungsversuch würde ich so argumentieren:
Wir wollen [mm] "\Leftarrow" [/mm] zeigen, dazu zeigen wir, dass wenn n keine Primzahl ist
(x + [mm] b)^{n} [/mm] nicht [mm] \equiv x^{n} [/mm] + [mm] b^{n} [/mm] mod n
sein kann. Nehmen wir also an n wäre keine Primzahl, also n zusammengesetzt. Nehmen wir weiter an, dass dann
(x + [mm] b)^{n} \equiv x^{n} [/mm] + [mm] b^{n} [/mm] mod n
so führt dies zu einem Widerspruch, denn für n = 2*2 gilt
(X + [mm] b)^{4} \equiv x^{4} [/mm] + 6*() + [mm] b^{4} [/mm] mod 4
aber nicht (X + [mm] b)^{4} \equiv x^{4} [/mm] + [mm] b^{4} [/mm] mod 4.
Demnach muss (x + [mm] b)^{n} [/mm] nicht [mm] \equiv x^{n} [/mm] + [mm] b^{n} [/mm] mod n gelten.
Ist das korrekt oder habe ich hier einen Trugschluss eingebaut?
|
|
|
| |
|
Hallo,
> Als Lösungsversuch würde ich so argumentieren:
>
> Wir wollen [mm]"\Leftarrow"[/mm] zeigen, dazu zeigen wir, dass wenn
> n keine Primzahl ist
> (x + [mm]b)^{n}[/mm] nicht [mm]\equiv x^{n}[/mm] + [mm]b^{n}[/mm] mod n
>
> sein kann. Nehmen wir also an n wäre keine Primzahl, also
> n zusammengesetzt. Nehmen wir weiter an, dass dann
>
> (x + [mm]b)^{n} \equiv x^{n}[/mm] + [mm]b^{n}[/mm] mod n
>
> so führt dies zu einem Widerspruch, denn für n = 2*2
> gilt
>
> (X + [mm]b)^{4} \equiv x^{4}[/mm] + 6*() + [mm]b^{4}[/mm] mod 4
>
> aber nicht (X + [mm]b)^{4} \equiv x^{4}[/mm] + [mm]b^{4}[/mm] mod 4.
>
> Demnach muss (x + [mm]b)^{n}[/mm] nicht [mm]\equiv x^{n}[/mm] + [mm]b^{n}[/mm] mod n
> gelten.
>
> Ist das korrekt oder habe ich hier einen Trugschluss
> eingebaut?
Letzteres. Du schmeißt hier unzulässigerweise Widerspruchsbeweis und Widerlegung durch Gegenbeispiel durcheinander.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:35 Di 27.05.2014 | | Autor: | huberT |
ok, das hab ich mir schon gedacht :/
kann mir vielleicht jemand helfen, wie ich beim beweis weiterkomme?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:26 Mi 28.05.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
