Diskrete Mathematik: Widerspruchsbeweis a^(n-1) kongruent 1 mod n

11.05.2015, 10:12

Mr. Mr.

Diskrete Mathematik: Widerspruchsbeweis a^(n-1) kongruent 1 mod n

Meine Frage:
$\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$
$\begin{eqnarray*} a \in \left\{ 1,2,...,n-1\right\} \end{eqnarray*}$

Wenn $\begin{eqnarray*} a^{n-1} \equiv 1 \end{eqnarray*}$ $\begin{eqnarray*} mod \end{eqnarray*}$ $\begin{eqnarray*} n \end{eqnarray*}$ dann ist $\begin{eqnarray*} n \end{eqnarray*}$ eine Primzahl.

Ich soll ein Widerspruchsbeweis durchführen und zeigen, dass die Beziehung $\begin{eqnarray*} a^{n-1} \equiv 1 \end{eqnarray*}$ $\begin{eqnarray*} mod \end{eqnarray*}$ $\begin{eqnarray*} n \end{eqnarray*}$ für
Teiler von n nicht gelten kann.

Meine Ideen:
Ich habe keine Idee, aber ich kenne folgendes:

Ist das nicht der kleine Satz von Fermat?
Wenn $\begin{eqnarray*} n \end{eqnarray*}$ eine Primzahl ist, dann gilt $\begin{eqnarray*} a^{n} \equiv a \end{eqnarray*}$ $\begin{eqnarray*} mod \end{eqnarray*}$ $\begin{eqnarray*} n \end{eqnarray*}$
Wenn ist es durch $\begin{eqnarray*} a \end{eqnarray*}$ teile, dann kommt $\begin{eqnarray*} a^{n-1} \equiv 1 \end{eqnarray*}$ $\begin{eqnarray*} mod \end{eqnarray*}$ $\begin{eqnarray*} n \end{eqnarray*}$
$\begin{eqnarray*} a \end{eqnarray*}$ ist nicht teilerfremd zu $\begin{eqnarray*} n \end{eqnarray*}$ , wenn $\begin{eqnarray*} a \end{eqnarray*}$ Vielfache von $\begin{eqnarray*} n \end{eqnarray*}$ ist.
$\begin{eqnarray*} a^{n-1}(n-1)! \equiv (n-1)! \end{eqnarray*}$ $\begin{eqnarray*} mod \end{eqnarray*}$ $\begin{eqnarray*} n \end{eqnarray*}$
$\begin{eqnarray*} n \end{eqnarray*}$ kann $\begin{eqnarray*} (n-1)! \end{eqnarray*}$ nicht teilen, da $\begin{eqnarray*} n \end{eqnarray*}$ eine Primzahl ist.

Hilft mir das irgendwie weiter, oder bin ich gerade jenseits von der Lösung entfernt? Ich will keine Lösung, sondern will das verstehen, aber verstehen tu ich jetzt nicht viel gerade.

11.05.2015, 11:32

HAL 9000

Auf diesen Beitrag antworten »

Bitte präzisiere mal die zu beweisende Aussage: Sollst du nun

Zitat:

Wenn $\begin{eqnarray*} a^{n-1} \equiv 1\bmod n \end{eqnarray*}$ für ein $\begin{eqnarray*} a \in \left\{ 1,2,...,n-1\right\} \end{eqnarray*}$ gilt, dann ist $\begin{eqnarray*} n \end{eqnarray*}$ eine Primzahl.

oder doch

Zitat:

Wenn $\begin{eqnarray*} a^{n-1} \equiv 1\bmod n \end{eqnarray*}$ für alle $\begin{eqnarray*} a \in \left\{ 1,2,...,n-1\right\} \end{eqnarray*}$ gilt, dann ist $\begin{eqnarray*} n \end{eqnarray*}$ eine Primzahl.

beweisen? So wie du es oben dargestellt hast, klingt es wie die erste Variante - ich würde aber eher auf die zweite tippen: Schließlich ist die erste Aussage falsch.

11.05.2015, 17:47

Mr. Mr.

Auf diesen Beitrag antworten »

Für alle. Pardon, habe ich vergessen.

11.05.2015, 18:12

HAL 9000

Auf diesen Beitrag antworten »

Ok, das wäre geklärt.

Wie das, was du unter meine Ideen geschrieben hast, zum Beweis beitragen soll, verstehe ich nicht. Aber warum befolgst du nicht den dir gegebenen äußerst konkreten Hinweis

Zitat:

Original von Mr. Mr.
Ich soll ein Widerspruchsbeweis durchführen und zeigen, dass die Beziehung $\begin{eqnarray*} a^{n-1} \equiv 1 \end{eqnarray*}$ $\begin{eqnarray*} mod \end{eqnarray*}$ $\begin{eqnarray*} n \end{eqnarray*}$ für Teiler von n nicht gelten kann.

D.h., wir nbetrachten irgendeinen nicht trivialen Teiler $\begin{align*} a \end{align*}$ von $\begin{align*} n \end{align*}$ , also mit $\begin{align*} 1<a<n \end{align*}$ , so einen muss es ja für Nichtprimzahlen $\begin{align*} n \end{align*}$ geben. Nehmen wir nun an, dass $\begin{eqnarray*} a^{n-1} \equiv 1\bmod n \end{eqnarray*}$ gilt, so muss wegen $\begin{align*} a \mid n \end{align*}$ auch $\begin{eqnarray*} a^{n-1} \equiv 1\bmod a \end{eqnarray*}$ gelten...

11.05.2015, 19:52

Mr. Mr.

Auf diesen Beitrag antworten »

Ich habe mir deine Antwort angeschaut und verstehe sie nicht ganz.

Ich muss jetzt schauen, dass der Teiler $\begin{eqnarray*} a \end{eqnarray*}$ nicht für die Formel $\begin{eqnarray*} a^{n-1} \equiv 1\bmod n \end{eqnarray*}$ gelten kann.

$\begin{eqnarray*} 1<a<n \end{eqnarray*}$

n ist keine Primzahl

$\begin{eqnarray*} a \end{eqnarray*}$ teilt $\begin{eqnarray*} n \end{eqnarray*}$

$\begin{eqnarray*} a \end{eqnarray*}$ ist somit Teiler von $\begin{eqnarray*} n \end{eqnarray*}$

Ist $\begin{eqnarray*} n \end{eqnarray*}$ ein Vielfaches von $\begin{eqnarray*} a \end{eqnarray*}$ ?

Du sagst, dass

Zitat:

so muss wegen $\begin{eqnarray*} a|n \end{eqnarray*}$ auch $\begin{eqnarray*} a^{n-1} \equiv 1\bmod a \end{eqnarray*}$ gelten...

Bist du sicher? Wenn ich für $\begin{eqnarray*} a = 4 \end{eqnarray*}$ verwenden und $\begin{eqnarray*} n = 8 \end{eqnarray*}$ , dann kommt $\begin{eqnarray*} 0 \end{eqnarray*}$ Rest raus.

$\begin{eqnarray*} 4^{8-1} \equiv 0\bmod 4 \end{eqnarray*}$
$\begin{eqnarray*} 4^{8-1} \equiv 0\bmod 8 \end{eqnarray*}$

oder

$\begin{eqnarray*} 2^{8-1} \equiv 0\bmod 2 \end{eqnarray*}$
$\begin{eqnarray*} 2^{8-1} \equiv 0\bmod 8 \end{eqnarray*}$

Halt! Oder ist deine Antwort bereits der Widerspruchsbeweis? Es muss ja das gelten, tut es nicht, als ist es ein Widerspruch. Habe ich Recht?

11.05.2015, 21:03

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Mr. Mr.
Du sagst, dass

Zitat:

so muss wegen $\begin{eqnarray*} a|n \end{eqnarray*}$ auch $\begin{eqnarray*} a^{n-1} \equiv 1\bmod a \end{eqnarray*}$ gelten...

Bist du sicher?

Ja, ICH BIN SICHER! Forum Kloppe

$\begin{eqnarray*} a^{n-1} \equiv 1\bmod n \end{eqnarray*}$ ist gleichbedeutend mit $\begin{eqnarray*} n \mid k \end{eqnarray*}$ für $\begin{eqnarray*} k=a^{n-1}-1 \end{eqnarray*}$ . Und dass

$\begin{eqnarray*} a \mid n \,\wedge\, n \mid k \;\Rightarrow\; a \mid k \end{eqnarray*}$

gilt, ist aller-, allerelementarste Teilbarkeitseigenschaft.

P.S.: Dein "Beispiel" ist Blödsinn - wir reden nur über $\begin{align*} a,n \end{align*}$ mit $\begin{align*} a^{n-1}\equiv 1\bmod n \end{align*}$ , was dein $\begin{align*} a=4,n=8 \end{align*}$ doch gar nicht erfüllt. Finger2

11.05.2015, 21:56

Mr. Mr.

Auf diesen Beitrag antworten »

Hmm...

Zitat:

$\begin{eqnarray*} a \mid n \,\wedge\, n \mid k \;\Rightarrow\; a \mid k \end{eqnarray*}$

kannte ich.

Das kannte ich nicht:

Zitat:

$\begin{eqnarray*} a^{n-1} \equiv 1\bmod n \end{eqnarray*}$ ist gleichbedeutend mit $\begin{eqnarray*} n \mid k \end{eqnarray*}$ für $\begin{eqnarray*} k=a^{n-1}-1 \end{eqnarray*}$

Ich kenne nur mit $\begin{eqnarray*} n \end{eqnarray*}$

$\begin{eqnarray*} a\cdot b\equiv 1 \end{eqnarray*}$ $\begin{eqnarray*} mod \end{eqnarray*}$ $\begin{eqnarray*} n \end{eqnarray*}$

$\begin{eqnarray*} n|a\cdot b - 1 \end{eqnarray*}$

$\begin{eqnarray*} a \cdot b - 1 = k \cdot n \end{eqnarray*}$

Du hast es ohne $\begin{eqnarray*} n \end{eqnarray*}$ geschrieben, weil ja $\begin{eqnarray*} n|k \end{eqnarray*}$ , denke ich.

Ich setzte mich nochmals dran, lese mir alle Regeln nochmal durch und durchblättere meine ganzen Mitschriften/Skripten. Werde wahrscheinlich morgen wieder schreiben. Wenn ich etwas habe, melde ich mich morgen wieder! Du kannst jetzt mal Gute Nacht sagen smile

11.05.2015, 22:24

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Mr. Mr.
Das kannte ich nicht:

Zitat:

$\begin{eqnarray*} a^{n-1} \equiv 1\bmod n \end{eqnarray*}$ ist gleichbedeutend mit $\begin{eqnarray*} n \mid k \end{eqnarray*}$ für $\begin{eqnarray*} k=a^{n-1}-1 \end{eqnarray*}$

Also nochmal zurück in die Kinderstube der Modulorechnung - scheint bei dir nötig zu sein:

Dir ist doch hoffentlich bewusst, dass $\begin{align*} u\equiv v\bmod n \end{align*}$ äquivalent ist zu $\begin{align*} n \mid (v-u) \end{align*}$ , so ist das schließlich DEFINIERT.

Nichts anderes habe ich hier doch für $\begin{align*} u=a^{n-1} \end{align*}$ und $\begin{align*} v=1 \end{align*}$ angewandt. böse

P.S.: Irgendwie ist es frustrierend, sich bei immer lächerlicher werdenden Kleinigkeiten aufzuhalten, während das Ziel in weite Ferne rückt.

11.05.2015, 22:54

Mr. Mr.

Auf diesen Beitrag antworten »

Das mit u und v kenne ich, nur zu spät gesehen. Es tut mir Leid, dass du wegen mir diesen Text geschrieben hast. Übrigens hast du einmal u und v vertauscht.

Ich weiß, das solche "Kleinigkeiten" nerven. Z.B. Überschrift ist nicht gleich Inhalt. Oder man verzichtet auf eine schöne Formatierung, auf die Art: Passt schon, machen die schon. Ich kenne das auch, deswegen habe ich auch "Gute Nacht" geschrieben und will mir alles nochmal durchlesen, damit du dich nicht so "direkt" wirst.

Am Anfang warst du geduldig, aber als ich ein paar mal geantwortet habe, hast du dir wahrscheinlich gedacht: Oh, Mann, schon wieder einer, der nichts lernt und keine Ahnung hat. Trotzdem hast du geantwortet, weil du helfen willst. Es war ein bisschen direkt, aber du hast geholfen. Ich bemühe mich, es zu verstehen und gehe alles nochmal durch. Ich entschuldige mich nochmals für diese Kleinigkeit. Morgen werde ich es weiter versuchen und meinen Fortschritt hier her posten. Ich werde versuchen, ein möglichst gut beschriebenen Lösungsversuch präsentieren. Oder gar die Lösung? ^^

11.05.2015, 22:58

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Mr. Mr.
Übrigens hast du einmal u und v vertauscht.

Einmal mehr dummes Zeug, was du da äußerst - da die Aussagen eh symmetrisch bzgl. u,v sind, kann man da gar nichts falsch vertauschen.

Ich schätze es überhaupt nicht, wenn jemand in altkluger Weise Ratschläge erteilt wie "Bist du sicher" oder "du hast da was vertauscht", die voll für die Tonne sind, weil er überhaupt keine Ahnung hat. Also nachfragen und lernen, aber nicht in dieser Weise dauernd grundlos die Kompetenz des Helfers in Frage stellen. böse

11.05.2015, 23:07

Mr. Mr.

Auf diesen Beitrag antworten »

Wahrscheinlich ist es noch reflexiv und transitiv oder sonst irgendwas.

12.05.2015, 21:56

Mr. Mr.

Auf diesen Beitrag antworten »

Sei $\begin{eqnarray*} n\in \mathbb N \end{eqnarray*}$ , $\begin{eqnarray*} a\in \left\{ 1,2,..n-1\right\}: \end{eqnarray*}$

Nehmen wir an, das $\begin{eqnarray*} n\in \mathbb P \end{eqnarray*}$

$\begin{eqnarray*} a^{n-1} \equiv mod n \end{eqnarray*}$

$\begin{eqnarray*} a^{n-1} mod n = 1 mod n \end{eqnarray*}$

Ich verwende den Euklid (hier bin ich mir nicht sicher, ob das so geht):

$\begin{eqnarray*} a^{n-1} = q_{1}n + r \end{eqnarray*}$
$\begin{eqnarray*} 1 = q_{2}n + r \end{eqnarray*}$

$\begin{eqnarray*} a^{n-1} - 1 = (q_{1} - q_{2})n \end{eqnarray*}$

Durch den Euklid wissen wir:

$\begin{eqnarray*} a^{n-1} = qn + 1 \end{eqnarray*}$

$\begin{eqnarray*} ggT(a^{n-1},n) = ggT(n,1) = 1<br /> \Rightarrow ggT(x,n) = 1 \end{eqnarray*}$

Und das gilt für alle $\begin{eqnarray*} x <=> n \in \mathbb P \end{eqnarray*}$

Ist das so richtig?

Ich wollte mit n ist kein Primzahl starten. Aber keine Ahnung.
Und ich wollte nie deine Kompetenz infrage stellen. NIEMALS. Es hat nur gezeigt, dass ich absolut keine Ahnung habe. Sorry.

13.05.2015, 08:48

HAL 9000

Auf diesen Beitrag antworten »

Ich entnehme deinem letzten Beitrag nichts, was in irgendeiner Weise zielführend für das anstehende Problem ist. Sondern nur, dass du alle fachlichen Hinweise im Thread (und in der Aufgabenstellung) vollständig außer Acht gelassen hast.

Es deutet alles darauf hin, dass du nicht den blassesten Schimmer hast, wie hier der Beweisgedanke ist. Vermutlich weißt du nicht mal, was mit "Widerspruchsbeweis" (=indirekter Beweis) gemeint ist - hier bitte mal nachlesen:

http://de.wikipedia.org/wiki/Beweis_%28M...direkter_Beweis

Im vorliegenden Fall soll ja bewiesen werden, dass aus der Aussage $\begin{align*} a^{n-1}\equiv 1\bmod n \end{align*}$ für alle $\begin{align*} a\in\{1,\ldots,n-1\} \end{align*}$ folgt, dass $\begin{align*} n \end{align*}$ eine Primzahl sein muss. Beim indirekten Beweis nehmen wir das Gegenteil an, d.h., dass es eine Nichtprimzahl $\begin{align*} n \end{align*}$ mit dieser Eigenschaft gibt. Jetzt nehmen wir irgendeinen Teiler $\begin{align*} a \end{align*}$ von $\begin{align*} n \end{align*}$ mit $\begin{align*} 1<a<n \end{align*}$ her (den es ja geben muss, wenn $\begin{align*} n \end{align*}$ keine Primzahl ist) und weisen für den nach, dass $\begin{align*} a^{n-1}\not\equiv 1\bmod n \end{align*}$ ist. Damit haben wir einen Widerspruch zur Voraussetzung, womit die Annahme "es gibt eine Nichtprimzahl n mit..." zu Fall gebracht ist, und der Beweis ist fertig.

Neue Frage »

Antworten »

Diskrete Mathematik: Widerspruchsbeweis a^(n-1) kongruent 1 mod n

Verwandte Themen