Forum:  Olympiade-Aufgaben
Thema: DeMO Bundesrunde - 571245- Zahlentheorie
Themen-Übersicht
Ankisa
Junior
Dabei seit: 08.06.2014
Mitteilungen: 20
Aus:
Themenstart: 2018-11-29 19:47

Ich bin zufällig über folgende Aufgabe gestolpert, fand sie sehr interessant und wollte sie sofort lösen. Das mit dem Sofort-Lösen hat leider nicht so toll funktioniert. Ich denke nun schon seit ein paar Tagen über das Problem nach und mache nicht wirklich Fortschritte. Daher wäre ich sehr glücklich, wenn mir jemand helfen könnte.

Zur Aufgabe:

Eine Folge positiver ganzer Zahlen <math>a_1, a_2, a_3, \dots</math> wird gebildet, indem man mit <math>a_1 = 1</math> beginnt
und schrittweise für <math>k = 2, 3, \dots </math> die Zahl <math>a_k</math> als größten Primteiler von <math>1 + a_1a_2 \dots a_{k-1}</math>
definiert. Man zeige, dass die Zahl <math>11</math> nicht in der Folge enthalten ist.

Ich habe bisher folgendes herausfinden bzw. zeigen können:

1. Diese Folge ist die zweite Euclid–Mullin Folge, nachlesbar hier: en.wikipedia.org/wiki/Euclid%E2%80%93Mullin_sequence
2. Leicht zu zeigen: Eine Zahl in der Folge taucht höchstens einmal auf.
3. Auch relativ leicht zu zeigen: Die Zahl 5 taucht nicht in der Folge auf.


robertoprophet
Senior
Dabei seit: 18.12.2006
Mitteilungen: 2023
Aus:
Beitrag No.1, eingetragen 2018-11-30 16:00

Ich finde die Aufgabe auch interessant. Deine 2. Aussage kann ich nachvollziehen. Wie aber zeigst du 3 (die Aussage stimmt natürlich)?


Kezer
Senior
Dabei seit: 04.10.2013
Mitteilungen: 904
Aus:
Beitrag No.2, eingetragen 2018-11-30 16:39

Hey,

die Aussage für $5$ war tatsächlich die Aufgabe für die 11. Klasse.

Ich habe diese Aufgabe vor einigen Monaten gelöst, aber soweit ich mich erinnern kann, ist das die (/eine) zielführende Idee:

Es müsste gelten $a_1 \dots a_k = 2^a 3^b 5^c 7^d 11^e - 1$. Bei den meisten Exponenten schließt man unmittelbar, dass sie trivial sind. Um das Argument zu Ende zu führen, braucht man noch bisschen Zahlentheorie.  😄


Ankisa
Junior
Dabei seit: 08.06.2014
Mitteilungen: 20
Aus:
Beitrag No.3, vom Themenstarter, eingetragen 2018-11-30 17:02

2018-11-30 16:00 - robertoprophet in Beitrag No. 1 schreibt:
Ich finde die Aufgabe auch interessant. Deine 2. Aussage kann ich nachvollziehen. Wie aber zeigst du 3 (die Aussage stimmt natürlich)?

Man nimmt an, dass für ein bestimmtes $n$ gilt: $a_n = 11$, dann folgt daraus, dass: $ 2^a * 3^b * 5^c = 1+ a_1 * \dots * a_{n-1}$. Nun aber sieht man: $2$ und $3$ teilen die linke Seite, aber nicht die Rechte, wenn $a,b \gt 0$.

Damit bekommst du: \(5^c = 1+ a_1 * \dots * a_{n-1} \Leftrightarrow
5^c -1 =a_1 * \dots * a_{n-1} \) und $c \gt 0$ , das Produkt der ersten $a_k$ ist ja bereits $\gt 5^1$

Nun sieht man aber: Linke Seite ist durch $4$ teilbar, die rechte Seite aber nicht. Ergo: $5$ kann nicht in der Folge auftauchen.


Ankisa
Junior
Dabei seit: 08.06.2014
Mitteilungen: 20
Aus:
Beitrag No.4, vom Themenstarter, eingetragen 2018-11-30 17:14

2018-11-30 16:39 - Kezer in Beitrag No. 2 schreibt:
Hey,

die Aussage für $5$ war tatsächlich die Aufgabe für die 11. Klasse.

Ich habe diese Aufgabe vor einigen Monaten gelöst, aber soweit ich mich erinnern kann, ist das die (/eine) zielführende Idee:

Es müsste gelten $a_1 \dots a_k = 2^a 3^b 5^c 7^d 11^e - 1$. Bei den meisten Exponenten schließt man unmittelbar, dass sie trivial sind. Um das Argument zu Ende zu führen, braucht man noch bisschen Zahlentheorie.  😄

Dass hierin eine bzw. die zielführende Idee liegt bezweifel ich nicht. Auf Wikipedia gibt es, denke ich auch, eine Referenz zum Originalpaper von 1957 (?), in dem das (und die allgemeinere Aussage, dass unendlich viele Primzahlen in dieser Folge fehlen.)
Für die allgemeinere Aussage wurde keine wirklich große Magie verwendet - das für mich Erstaunliche war eher, wie viel man bereits mit relativ wenig Mathematik zeigen kann, wenn man erst gut beobachtet und dann clever argumentiert.
Ich hatte trotzdem insgeheim gehofft, dass es die Aufgabe, im Falle für die $11$, ähnlich schnell/einfach lösen lässt, wie für den Fall mit $5$ :/


Ex_Senior
Neu
Dabei seit: 00.00.0000
Mitteilungen: 0
Aus:
Beitrag No.5, eingetragen 2018-11-30 18:14

Moin Ankisa,

man kann auch vergleichsweise einfach zeigen, dass auch die 11 nicht auftaucht:


Wegen $a_1=1, a_2=2, a_3=3, a_4=7$ müsste für ein potentielles $a_n=11$ zumindest einmal $n>4$ gelten. Insbesondere ist $P:=a_1 \cdot \dots \cdot a_{n-1}$ durch 2, 3 und 7 teilbar, also $P + 1$ nicht und damit $P+1=5^k \cdot 11^l$ mit nicht-negativen ganzen Zahlen $k$ und $l$.

Da bis auf $a_2$ alle Faktoren von $P$ ungerade sind -- wie man leicht aufgrund der paarweisen Teilerfremdheit der $a_i$ beweist -- , ist $P$ durch 2, aber nicht 4 teilbar, also $\equiv 2 \pmod{4}$ und damit $P+1 \equiv 3 \pmod{4}$. Da $P+1=5^k \cdot 11^l \equiv 1^k \cdot 3^l \pmod{4}$ gilt, ist $l$ ungerade.

Wegen $3|P$ folgt $1 \equiv P+1=5^k \cdot 11^l \equiv (-1)^k \cdot (-1)^l = (-1)^{k+l} \pmod{3}$, also zusammen mit $l$ ungerade auch $k$ ungerade.

Schließlich ist analog wegen $7|P$ auch $1 \equiv P+1 \equiv (-2)^k \cdot 4^l = (-2)^{k+2l} \pmod{7}$, was zum Widerspruch führt, da $k+2l$ ungerade ist, aber wegen $(-2)^2\equiv 4 \pmod{7}$ und $(-2)^3 \equiv -1 \pmod{7}$ eine Potenz von (-2) nur dann kongruent 1 modulo 7 sein kann, wenn der Exponent durch 7-1=6 teilbar, und also insbesondere gerade ist.

(Das war mein erster Aufgabenvorschlag, der es bis auf eine Bundesrunde geschafft hat. :) )

Cyrix


weird
Senior
Dabei seit: 16.10.2009
Mitteilungen: 5301
Aus:
Beitrag No.6, eingetragen 2018-11-30 22:54

Ja, ist eine hübsche Aufgabe und man kann sich vorstellen, wie man auch andere Fälle ähnlich löst, auch wenn es dann wohl immer komplizierter wird.  😉

Was ich aber nicht wirklich verstehe, obwohl das jetzt vielleicht ein bißchen nach nitpicking aussehen mag, ist die Tatsache, dass man die Folge hier mit 1 statt mit 2 beginnen lässt. Weder ist nämlich die 1 eine Primzahl, wie die anderen Folgenglieder, noch leistet sie hier auch nur irgendeinen Beitrag, außer die Folge unnötig zu verlängern. Von daher würde ich sie hier aus der Folge entfernen, ohne auch nur eine Sekunde zu überlegen.   😎



Ankisa
Junior
Dabei seit: 08.06.2014
Mitteilungen: 20
Aus:
Beitrag No.7, vom Themenstarter, eingetragen 2018-12-01 14:57

Cyrix, wow, vielen Dank :)

Die Aufgabe war tatsächlich so einfach lösbar! Das wirft für mich die Frage, wieso ich das Argument von dir nicht rigorus durchziehen konnte  😵
(Für mich heißt das: Ich brauche mehr Übung!)




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=238978=16
Druckdatum: 2020-09-27 11:23