Induktionsbeweis (Primfaktoren)

12.02.2020, 18:30

manuel459

Induktionsbeweis (Primfaktoren)

Hi,

wenn a eine ungerade natürliche Zahl größer drei ist, ist die Anzahl der verschiedenen Primfaktoren von $\begin{eqnarray*} a^{2^n}-1 \end{eqnarray*}$ mindestens n+1.

Ich kann da folgenden Induktionsschritt nicht nachvollziehen:

Nach der 3. binomischen Formel ist $\begin{eqnarray*} a^{2^{n+1}}-1=(a^{2^n}-1)(a^{2^n}+1) \end{eqnarray*}$ . Die Zahlen $\begin{eqnarray*} \frac{a^{2^n}-1}{2} \end{eqnarray*}$ und $\begin{eqnarray*} \frac{a^{2^n}+1}{2} \end{eqnarray*}$ sind Nachbarn, also haben sie keine gemeinsamen Primfaktoren. Soweit so gut. Schreibt man nun $\begin{eqnarray*} (a^{2^n}-1)(a^{2^n}+1)=4\frac{(a^{2^n}-1)}{2}\frac{(a^{2^n}+1)}{2} \end{eqnarray*}$ (das darf man, da die Zahlen im Zähler gerade sind) so hat diese Zahl also mindestens n+2 verschiedene Primfaktoren.

Nun sehe ich den letzten Schritt einfach nicht. Aus meiner Sicht erhalte ich daraus, dass die Brüche Nachbarn sind, und aus der Induktionsvoraussetzung nur, dass $\begin{eqnarray*} \frac{(a^{2^n}-1)}{2} \end{eqnarray*}$ mind. n verschiedene Primfaktoren hat (man dividiert ja durch 2 und könnte so den Primfaktor 2 entfernen). Multipliziert man dann mit dem anderen Bruch, so kommt ja nur ein Primfaktor hinzu (aufgrunddessen, dass die oben genannten Zahlen Nachbarn sind). Die Multiplikation mit 4 ergänzt hingegen keinen weiteren "neuen" Primfaktor, da die beiden Brüche ja nicht notwendigerweise ungerade sein müssen.

Jemand eine Idee?

Danke und LG

12.02.2020, 18:41

HAL 9000

Auf diesen Beitrag antworten »

Wir sind uns doch darüber einig, dass im Fall $\begin{eqnarray*} n\geq 1 \end{eqnarray*}$ beim Übergang $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ mindestens ein ungerader Primfaktor hinzukommt? (*)

Bleibt also lediglich nachzuweisen, dass man im Fall $\begin{eqnarray*} n=1 \end{eqnarray*}$ mindestens zwei Primfaktoren hat. Dazu benötigt man $\begin{eqnarray*} a>3 \end{eqnarray*}$ , denn im Fall $\begin{eqnarray*} a=3 \end{eqnarray*}$ ist das wegen $\begin{eqnarray*} 3^2-1=8=2^3 \end{eqnarray*}$ nicht der Fall.

12.02.2020, 22:25

manuel459

Auf diesen Beitrag antworten »

ich verstehe leider nach langer Überlegung immer noch nicht, wie das hilft. Könntest du das noch etwas genauer erklären, wie der ungerade Primfaktor (der hinzukommt) in diese Überlegung einfließt?

Danke

12.02.2020, 22:40

HAL 9000

Auf diesen Beitrag antworten »

Die Induktionsvoraussetzung sagt, dass $\begin{eqnarray*} \left(a^{2^n}-1\right) \end{eqnarray*}$ mindestens (n+1) Primfaktoren aufweist.

Nun sind wie oben erwähnt $\begin{eqnarray*} \frac{a^{2^n}-1}{2} \end{eqnarray*}$ und $\begin{eqnarray*} \frac{a^{2^n}+1}{2} \end{eqnarray*}$ aufeinander folgende natürliche Zahlen und damit teilerfremd. Das heißt dann insbesondere, dass die ungeraden Primfaktoren von $\begin{eqnarray*} \left(a^{2^n}+1\right) \end{eqnarray*}$ von allen Primfaktoren von $\begin{eqnarray*} \left(a^{2^n}-1\right) \end{eqnarray*}$ verschieden sein müssen.

Es bleibt im Induktionsschritt also lediglich zu zeigen, dass es mindestens einen solchen ungeraden Primfaktor gibt, m.a.W., dass $\begin{eqnarray*} \left(a^{2^n}+1\right) \end{eqnarray*}$ keine Zweierpotenz sein kann. Und das folgt im Fall $\begin{eqnarray*} n\geq 1 \end{eqnarray*}$ durch eine Betrachtung modulo 4:

$\begin{eqnarray*} a^{2^n}+1 = \left(a^{2^{n-1}}\right)^2+1 \equiv (\pm 1)^2+1 = 2\bmod 4 \end{eqnarray*}$

unter Beachtung von $\begin{eqnarray*} a^{2^n}+1\geq a^2+1\geq 26 \end{eqnarray*}$ .

Viel wichtiger ist eigentlich hier der Induktionsanfang

Zitat:

Original von HAL 9000
Bleibt also lediglich nachzuweisen, dass man im Fall $\begin{eqnarray*} n=1 \end{eqnarray*}$ mindestens zwei Primfaktoren hat.

Dazu reicht es zu zeigen, dass der entsprechende Term $\begin{eqnarray*} \left(a^2-1\right) \end{eqnarray*}$ neben 2 auch noch mindestens einen ungeraden Primfaktor enthält.

12.02.2020, 23:38

manuel459

Auf diesen Beitrag antworten »

Vielen Dank. Habe das alles soweit nun auch für mich nachvollziehen und genau hinschrieben können. Warum ist es denn notwendig, dass für n=1 die Zahl $\begin{eqnarray*} a^2-1 \end{eqnarray*}$ mindestens einen ungeraden Primfaktor hat? Das verwendet man im Induktionsschritt doch nirgends?

13.02.2020, 06:38

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von manuel459
Warum ist es denn notwendig, dass für n=1 die Zahl $\begin{eqnarray*} a^2-1 \end{eqnarray*}$ mindestens einen ungeraden Primfaktor hat? Das verwendet man im Induktionsschritt doch nirgends?

Zum x-ten Male: Das ist der InduktionsANFANG !!!

Für n=1 benötigen wir mindestens (n+1)=2 verschiedene Primfaktoren - wie willst du das denn ohne ungerade Primfaktoren schaffen? Forum Kloppe

Nehmen wir z.B. das bereits angesprochene Beispiel $\begin{eqnarray*} a=3 \end{eqnarray*}$ : Auch für dieses $\begin{eqnarray*} a \end{eqnarray*}$ klappt der Induktionsschritt ("ein Primfaktor mehr als beim Vorgänger"), aber der Induktionsanfang $\begin{eqnarray*} n=1 \end{eqnarray*}$ misslingt:

$\begin{eqnarray*} n=1:\; 3^{2^1}-1 = 8 = 2^3 \end{eqnarray*}$ nur 1 Primfaktor statt der geforderten $\begin{eqnarray*} \geq 2 \end{eqnarray*}$

$\begin{eqnarray*} n=2:\; 3^{2^2}-1 = 80 = 2^4\cdot 5 \end{eqnarray*}$ nur 2 Primfaktoren statt der geforderten $\begin{eqnarray*} \geq 3 \end{eqnarray*}$

$\begin{eqnarray*} n=3:\; 3^{2^3}-1 = 6\,560 = 2^5\cdot 5\cdot 41 \end{eqnarray*}$ nur 3 Primfaktoren statt der geforderten $\begin{eqnarray*} \geq 4 \end{eqnarray*}$

$\begin{eqnarray*} n=4:\; 3^{2^4}-1 = 43\,046\,720 = 2^6\cdot 5\cdot 17\cdot 41\cdot 193 \end{eqnarray*}$ mit 5 Primfaktoren, endlich im Soll

D.h., es kommt zwar immer von Schritt zu Schritt mindestens ein neuer Primfaktor hinzu, aber der "Rückstand" zum Anfang n=1 wird erst bei n=4 wieder aufgeholt, dank dort dann zufälligerweise zwei neuen Primfaktoren statt nur einem. Wegen dieses misslungenen Starts musste $\begin{eqnarray*} a=3 \end{eqnarray*}$ in den Voraussetzungen ausgeschlossen werden.

13.02.2020, 10:13

manuel459

Auf diesen Beitrag antworten »

Jetzt habe ich es verstanden. Da hatte ich wohl einen Knoten im Kopf...

Danke für die Geduld Big Laugh

Neue Frage »

Antworten »

Induktionsbeweis (Primfaktoren)

Verwandte Themen