2^p + 1 durch 3 teilbar

31.05.2018, 11:08	Rup	Auf diesen Beitrag antworten »
2^p + 1 durch 3 teilbar Meine Frage: Hallo, mit einem Beweis, der bestimmt total einfach ist, habe ich Probleme: Sei p eine Primzahl >= 5. Zeige, dass $\begin{eqnarray} 2^{p}+1 \end{eqnarray}$ durch 3 teilbar ist. Meine Ideen: Ich komme einfach nicht drauf. Meine erste Idee war der kleine Satz von Fermat, nach dem ja $\begin{eqnarray} 2^{p} \equiv 2 mod p \end{eqnarray}$ . Aber was modulo p ist, interessiert ja nicht wirklich und sagt nichts über die Teilbarkeit durch 3 aus. Könnte mir jemand einen Tipp geben?
31.05.2018, 11:11	tatmas	Auf diesen Beitrag antworten »
Hallo, welchen modulus musst du bei Teilbarkeit durch 3 betrachten?
31.05.2018, 11:31	Rup	Auf diesen Beitrag antworten »
Naja, wenn ich wüsste, dass der Ausdruck 0 mod 3 ist, dann wäre er ja durch 3 teilbar. Ich weiß nur nicht, wie ich irgendwelche Aussagen über modulo 3 machen kann.
31.05.2018, 11:34	HAL 9000	Auf diesen Beitrag antworten »
Wie so oft kann man auch hier anmerken: Es wird einfach zu wenig probiert! Es soll sofort der große Wurf gelingen, mit Fermat oder sonstwiewas. Wenn man einfach mal $\begin{eqnarray} 2^k+1 \end{eqnarray}$ für die ersten paar Werte $\begin{eqnarray} k=0,1,2,3,\ldots \end{eqnarray}$ berechnet und die Teilbarkeit durch 3 prüft, da kommt man relativ schnell zur Erkenntnis, dass gar nicht die Primzahleigenschaft sondern die Ungeradheit von $\begin{eqnarray} k \end{eqnarray}$ ausschlaggebend ist. Und mit der Erkenntnis sollte dann auch der Beweis dessen rasch gelingen.
31.05.2018, 12:49	Rup	Auf diesen Beitrag antworten »
Vielen Dank für den Tipp! Wir haben uns in letzter Zeit so viel mit Primzahlen und ihren Eigenschaften beschäftigt, dass ich gar nicht auf die Idee gekommen bin, einfach mal alle Zahlen einzusetzen. Vor diesem Hintergrund mein Beweis (mit Induktion): Behauptung: Für alle ungeraden Zahlen u gilt: $\begin{eqnarray} 2^{u}+1 \end{eqnarray}$ ist durch $\begin{eqnarray} 3 \end{eqnarray}$ teilbar. Beweis: Induktionsanfang: u = 1: $\begin{eqnarray} 2^{1} + 1 = 3 \end{eqnarray}$ , also durch 3 teilbar. Induktionsannahme: Sei die Aussage für ein u bewiesen. Induktionsschritt: u -> u+2 $\begin{eqnarray} 2^{u+2} +1 = 4 \cdot 2^{u} + 1 = (3 \cdot 2^{u}) + (2^{u} + 1) \end{eqnarray}$ Der erste Summand ist offensichtlich durch 3 teilbar, und mit der Induktionsannahme ist auch der zweite Summand durch 3 teilbar. Daraus folgt, dass auch $\begin{eqnarray} 2^{u+2} \end{eqnarray}$ durch 3 teilbar ist, und die Behauptung ist bewiesen. Wenn die Behauptung für alle ungeraden Zahlen gilt, dann insbesondere auch für alle Primzahlen >=5. Dieser Beweis kommt mir zwar etwas umständlich vor, aber er sollte korrekt sein, oder?
31.05.2018, 13:17	HAL 9000	Auf diesen Beitrag antworten »
Der Beweis ist in Ordnung. Die Umständlichkeit eines Beweises hängt auch immer davon ab, welches Vorwissen man hat und benutzen darf. Ist man z.B. mit der Modulrechnung vertraut, so kann man das ganze wegen $\begin{eqnarray} 2\equiv -1\bmod 3 \end{eqnarray}$ auch abkürzen zu $\begin{eqnarray} 2^p+1 \equiv (-1)^p+1 = -1+1 = 0\bmod 3 \end{eqnarray}$ , wobei beim zweiten = die Ungeradheit von $\begin{eqnarray} p \end{eqnarray}$ genutzt wurde.
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »