OliForum Matematico

Comincio con un numero a più cifre $a_1$, e genero una sequenza $a_2,a_3,a_4...$. Qui $a_{n+1}$ viene da $a_n$ a cui è stata attaccata una cifra diversa da 9.
Allora non posso evitare il fatto che ci sono infiniti $a_i$ appartenenti alla sequenza che sono numeri composti (cioè non numeri primi).


Se aggiungo una tra le cifre appartenenti all'insieme {0,2,4,6,8,5} naturalmente ottengo un numero composto. Analizzo allora il caso i casi in cui aggiungo una delle cifre appartenenti all'insieme {1,3,7}: siccome $1\equiv 7 \equiv 1 \mod 3$, ogni volta che aggiungo al massimo 3 cifre appartenenti all'insieme {1,7}, intervellante da un numero qualsiasi di 3\equiv 0 (3), otterrò un multiplo di 3 , quindi un numero composto.
Quindi da un certo punto in poi dovrò per forza aggiungere soltanto dei 3, per sempre.

La soluzione he ho trovato dice adesso che se nella sequenza ottengo un primo $p$, allora se continuo ad aggiungere 3, quando avrò aggiunto la cifra 3 $p$ volte,sarò sicuro di avere ottenuto almeno un altro multiplo di $p$. Lo giustifica dicendo che gcd(10,p)=1 , ma non capisco il collegamento con tale fatto potete aiutarmi?

c'è un classico esercizio "da stage":

chi ha preparato almeno una lezione di teoria dei numeri ha scritto:Per ogni primo $p$ diverso da 2 e da 5 c'è un numero che si scrive con sole cifre 1 (in base 10) e divisibile per $p$.

riesci a dedurre quello che ti serve da questo?

Provo io Do per buoni tutti i ragionamenti già fatti da LukasEta.

Sia p un primo tale che $p|a_0$ (va bene anche $p=a_0$). Qui ho scelto $a_0$ nella situazione in cui posso aggiungere solo più 3.
Dalla definizione ricorsiva $a_n=10a_{n-1}+3$ ottengo subito $a_n=10^na_0+\frac{10^n-1}{3}$. A questo punto basta scegliere gli n divisibili per $ord_p(10)$ per ottenere numeri divisibili per p. Se il primo che ho scelto è 3 quel denominatore non dà comunque problemi essendo che $9|10^n-1$.

Un modo col pigeonhole (usando l'esercizio di ma_go) potrebbe essere sostituire la frase "scelgo i multipli dell'ordine" con "per l'esercizio qua sopra esistono infiniti n tali che $\displaystyle p|\frac{10^n-1}{9}|\frac{10^n-1}{3}$".