Satz von Euler "Gegenbeweis"

01.12.2016, 15:11	sherrie	Auf diesen Beitrag antworten »
Satz von Euler "Gegenbeweis" Hey Leute! Ich hoffe "Sonstiges" ist das richtige Forum, wenn nicht bitte ich um Verzeihung... Zum Problem. Wir sind Informatikstudenten und hassen Beweise... Leider kommen wir mit folgender Aufgabe nicht weiter: "Wieso kann eine natürliche Zahl n nicht pseudoprim bezüglich einer Zahl a sein, wenn $\begin{eqnarray} ggT(a, n) \neq 1 \end{eqnarray}$ gilt?" Der Prof weiß, dass keiner in seinem Kurs sowas selbst beantworten kann, deswegen hat er uns ein paar Tipps gegeben: n ist pseudoprim bzgl. a entspricht: $\begin{eqnarray} n \end{eqnarray}$ teilt $\begin{eqnarray} a^{n-1} - 1 \end{eqnarray}$ $\begin{eqnarray} nx = a^{n-1} - 1 \end{eqnarray}$ ggT(a,n) = 1 -> teilerfremd ggT(a,n)!= 1 -> es gibt einen ggT > 1 Beweise: Wenn es einen ggT > 1 gibt, kann $\begin{eqnarray} nx = a^{n-1} - 1 \end{eqnarray}$ nicht wahr sein. Den letzten Schritt müssen wir aber selbst lösen. Hat eine gute Seele einen Vorschlag wie man sowas beweist? LG, Sherrie
01.12.2016, 15:23	Elvis	Auf diesen Beitrag antworten »
Definiere d=ggT(a,n), dann hat das Kind einen Namen. d teilt n, also teilt d auch nx, das ist die linke Seite der Gleichung. d teilt a, kann d die rechte Seite der Gleichung teilen ? (Hinweis: vergleiche den Beweis von Euklid, der sagt, dass es unendlich viele Primzahlen gibt.)

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »