Matroids Matheplanet Forum Index
Moderiert von ZetaX Naphthalin
Mathematik » Olympiade-Aufgaben » DeMO Bundesrunde - 571245- Zahlentheorie
Druckversion
Druckversion
Autor
Universität/Hochschule J DeMO Bundesrunde - 571245- Zahlentheorie
Ankisa
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 08.06.2014
Mitteilungen: 20
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-11-29


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:
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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
robertoprophet
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 18.12.2006
Mitteilungen: 2023
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-11-30


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kezer
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.10.2013
Mitteilungen: 772
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2018-11-30


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.  😄


-----------------
The difference between the novice and the master is that the master has failed more times than the novice has tried. ~ Koro-Sensei



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ankisa
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 08.06.2014
Mitteilungen: 20
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2018-11-30


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ankisa
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 08.06.2014
Mitteilungen: 20
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2018-11-30


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$ :/



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ex_Senior
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2018-11-30


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 5301
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2018-11-30


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.   😎




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ankisa
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 08.06.2014
Mitteilungen: 20
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2018-12-01


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!)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ankisa hat die Antworten auf ihre/seine Frage gesehen.
Ankisa hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]