Beweis zu Primzahlen

08.05.2015, 16:48	led123	Auf diesen Beitrag antworten »
Beweis zu Primzahlen Meine Frage: Sei $\begin{eqnarray} n \in \mathbb N \end{eqnarray}$ . Wenn für alle $\begin{eqnarray} x \in {1,2,...,n-1} \end{eqnarray}$ gilt, dass $\begin{eqnarray} x^{n-1} \equiv 1 \end{eqnarray}$ mod $\begin{eqnarray} n \end{eqnarray}$ , dann ist $\begin{eqnarray} n \end{eqnarray}$ eine Primzahl. Meine Ideen: Sei $\begin{eqnarray} n \end{eqnarray}$ keine Primzahl. Dann existiert ein Teiler $\begin{eqnarray} t \end{eqnarray}$ für den gilt, dass $\begin{eqnarray} t \neq 1 \cap t \neq n \end{eqnarray}$ . $\begin{eqnarray} n \mid x^{n-1}-1 \Rightarrow t \mid x^{n-1}-1 \end{eqnarray}$ Jetzt hab ich mir überlegt ein passendes $\begin{eqnarray} x \end{eqnarray}$ zu wählen, sodass diese Eigenschaft verletzt wird. Mir fällt aber nichts passendes ein. Grüße, led123
08.05.2015, 16:57	HAL 9000	Auf diesen Beitrag antworten »
Erstmal nehme ich an, es geht nur um $\begin{align} n\geq 2 \end{align}$ , ansonsten wäre nach deiner Definition auch $\begin{align} n=1 \end{align}$ eine Primzahl. Die Idee mit dem $\begin{align} t \end{align}$ ist gut, von da an ist es doch einfach: Betrachte einfach $\begin{align} x=t \end{align}$ , d.h., zeige, dass für diesen Teiler $\begin{align} t \end{align}$ die Kongruenz $\begin{align} t^{n-1}\equiv 1\bmod n \end{align}$ gar nicht bestehen kann. P.S.: Ähnlich, aber nicht dasselbe: http://de.wikipedia.org/wiki/Carmichael-Zahl
08.05.2015, 18:11	led123	Auf diesen Beitrag antworten »
Danke HAL 9000! Soll ich dann besser $\begin{eqnarray} t \mid t^{n-1}-1 \end{eqnarray}$ oder $\begin{eqnarray} n \mid t^{n-1}-1 \end{eqnarray}$ betrachten? Ich sehe leider noch nicht, wie ich nun weiter komme. Habe auch probiert in die Definition des Teilers einzusetzen.
08.05.2015, 18:48	HAL 9000	Auf diesen Beitrag antworten »
Sonderlich sattelfest bist du aber nicht in Sachen Teilbarkeit: Wenn $\begin{align} n \mid (t^{n-1}-1) \end{align}$ gelten soll, und $\begin{align} t \mid n \end{align}$ gilt, dann muss auch $\begin{align} t \mid (t^{n-1}-1) \end{align}$ gelten - und das sollte sich doch leicht zum Widerspruch führen lassen!
08.05.2015, 18:54	led123	Auf diesen Beitrag antworten »
Danke! Ich hab ihn nun erkannt.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »