Beweis keine Primzahlen

17.08.2024, 08:11	Lama06	Auf diesen Beitrag antworten »
Beweis keine Primzahlen Meine Frage: Aufgabe 531224 der Mathe-Olympiade: Man beweise, dass keine der Zahlen 1, 1001, 1001001, 1001001001, 1001001001001 eine Primzahl ist. Meine Ideen: Ich habe diese Folge erstmal rekursiv dargestellt, also: a_1 := 1 a_(n+1) := 10^3a_n + 1 Dann stellt man Folgendes fest: a_(n+2) := 10^3a_(n+1) + 1 = 10^3(10^3a_n + 1) + 1 = 10^6a_n + 10^3 + 1 = 10^6a_n + a_2 Das bedeutet, dass schonmal alle a_(2k) mit k > 1 keine Primzahlen sind, weil man sie durch a_2 teilen kann. Das kann man auch verallgemeinern: a_(n+p) = 10^(3p) * a_n + a_p Das heißt, dass alle a_(k*p) mit k > 1 durch a_p teilbar sind. Das bedeutet, dass a_n keine Primzahl ist, wenn n keine Primzahl ist. Aber wie zeige ich, dass a_n keine Primzahl ist, wenn n eine Primzahl ist? Oder bin ich auf dem falschen Pfad?
17.08.2024, 09:07	IfindU	Auf diesen Beitrag antworten »
RE: keine Primzahlen: 1001, 1001001, 1001001001, ... Sieht ganz gut aus, aber es geht auch etwas einfacher bis dahin: Jede zweite Zahl hat die alternierende Quersumme von 0 und ist damit durch 11 teilbar. Jede dritte Zahl hat eine durch 3 teilbare Quersumme und ist durch 3 teilbar. Da alle Zahlen von der Form $\begin{eqnarray} 6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5 \end{eqnarray}$ sind, hat man nur noch $\begin{eqnarray} 6k\pm 1 \end{eqnarray}$ zu untersuchen. Hier weiß ich spontan auch nicht mehr weiter.
17.08.2024, 13:52	HAL 9000	Auf diesen Beitrag antworten »
Sei $\begin{eqnarray} a_n \end{eqnarray}$ diese Zahl mit genau $\begin{eqnarray} n \end{eqnarray}$ Einsen. Dann ist $\begin{eqnarray} a_n = \frac{10^{3n}-1}{1000-1} = \frac{\left(10^n-1\right)\left(10^{2n}+10^n+1\right)}{999} \end{eqnarray}$ . Es folgt $\begin{eqnarray} a_n = \frac{b_n\cdot c_n}{37} \end{eqnarray}$ mit den beiden ganzen Zahlen $\begin{eqnarray} b_n = \frac{10^n-1}{9} \end{eqnarray}$ und $\begin{eqnarray} c_n = \frac{10^{2n}+10^n+1}{3} \end{eqnarray}$ . Nun gilt entweder $\begin{eqnarray} 37\mid b_n \end{eqnarray}$ oder $\begin{eqnarray} 37\mid c_n \end{eqnarray}$ . Im ersten Fall ist $\begin{eqnarray} a_n \end{eqnarray}$ durch $\begin{eqnarray} c_n \end{eqnarray}$ teilbar, im zweiten durch $\begin{eqnarray} b_n \end{eqnarray}$ - beidesmal also keine Primzahl, zumindest für $\begin{eqnarray} n\geq 2 \end{eqnarray}$ .

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »