[L02/03] $111 \dots 111$

[Gerald Lambeau]

Forse è già passato, non ricordo, comunque:
dimostrare che per ogni $n$ intero positivo coprimo con $2$ e con $5$ esiste un numero la cui scrittura decimale è composta dalla cifra $1$ ripetuta (un numero della forma $111 \dots 111$) che sia multiplo di $n$.
E per i più impavidi asserisco che (non leggere se non si è già risolto il problema)

Testo nascosto:

esiste una soluzione che non usa Eulero-Fermat, decisamente elementare (e si scoprì in seguito che la conoscevano tutti, anzi, che tutti ne conoscevano una ancor più semplice...)

.

[Rho33]

Bene, la soluzione per questo esercizio è apparentemente lunga, soltanto perchè generalizzo un teorema molto famoso:

Testo nascosto:

Step 1 Per prima cosa dimostriamo il Piccolo Teorema di Fermat, che poi generalizziamo ad un $n$ generico.

$a^{p-1} \equiv 1 \pmod p$ con $(a,p)=1$

Soluzione: Sia $a$ un intero positivo tale che $(a,p)=1$. Consideriamo la sequenza $1,2,3,...,p-1$ , si osservi che tutti gli elementi di essa sono coprimi con $p$ . Consideriamo ora la sequenza precedente moltiplicata per $a$ , ovvero $a,2a,3a,...,(p-1)a$ , anche tutti i suoi elementi sono coprimi con $p$ ( inoltre entrambe le sequenze contengono esattamente $(p-1)$ elementi) .

Guardiamo ora la seconda sequenza modulo $p$ : per quanto detto in precedenza, i resti degli elementi divisi per $p$ , possono essere trovati solamente tra gli elementi della prima sequenza. Supponiamo inoltre che due elementi della seconda sequenza siano congrui modulo $p$ , ovvero che valga $ka \equiv ha \pmod p$ , allora, dato che $(a,p)=1 \rightarrow k \equiv h \pmod p$ ma $k,h$ sono diversi, minori di $p$ e coprimi con $p$ , quindi $k=h$ . Segue quindi che i resti della seconda sequenza modulo $p$ sono tutti e soli gli elementi della prima sequenza, quindi la seconda sequenza è semplicemente una possibile permutazione della prima.

Chiaramente deve valere che $a \cdot 2a \cdot 3a \cdot ... \cdot (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdot ... \cdot (p-1) \pmod p \iff a^{p-1} \equiv 1 \pmod p$


Step 2: Generalizziamo il FLT ad un $n$ generico, riciclando la dimostrazione precedente ( per questo mi sono preso la briga di scriverla )

$a^{\varphi(n)} \equiv 1 \pmod n$ con $(a,n)=1$

Soluzione: identica alla dimostrazione precedente ma stavolta le sequenze da considerare sono $c_1,c_2,c_3,...,c_{\varphi (n)}$ (l'insieme degli interi positivi minori di $n$ e coprimi con $n$) e $ ac_1,ac_2,ac_3,...,ac_{\varphi (n)}$ ( la prima sequenza moltiplicata per $a$). Ah, dimenticavo, $\varphi (n)$ è la solita funzione di Eulero ovviamente


Step 3: risolviamo il vero problema ! Chiaramente un numero in quella forma si può scirvere come

$10^m+10^{m-1}+...+10+1= \dfrac {10^{m+1}-1}{9}$ . Osserviamo ora $(10,n)=1$ dove $n$ è quello dell'esercizio. Voglio che quella frazione sia divisibile per $n$ per qualunque $n$ coprimo con $2,5$. Ma ora basta scegliere $m+1= \varphi (9\cdot n)$ e per lo step 2 , $10^{m+1} \equiv 1 \pmod {9 \cdot n}$ . Cioè la frazione è divisibile per $n$ !

[alexthirty]

La soluzione è giusta... Tra l'altro penso proprio che a gare come Cesenatico si possa dare per scontato Fermat e Eulero-Fermat

[Gerald Lambeau]

Buona! Ora fatela con solo strumenti elementari.

[Rho33]

Un esercizio molto molto simile e carino è questo: dimostrare che nella progressione aritmetica di ragione $729$ e primo termine $1$ vi sono infinite potenze di $10$ .

[Drago]

Spoilero il problema originale, e in realtà quello nuovo si fa nello stesso modo...

Testo nascosto:

Scriviamo i numeri $1,11,111,\dots$ fino a quello con $n+1$ uni, chiamandoli $a_1,\dots,a_{n+1}$. Guardiamo il resto di ognuno nella divisione per $n$: ho $n$ possibili resti, ma $n+1$ numeri, ergo due di questi avranno lo stesso resto, diciamo $a_i,a_j$ con $i>j$. Ma allora se ne faccio la differenza avrò un multiplo di $n$; tuttavia la differenza sarà una cosa del tipo $a_i-a_j=1\dots10\dots0=10^j\cdot a_{i-j}$ con $i-j$ uni e $j$ zeri. Dato che $(n,10)=1$ vale in generale $n\mid 10m\iff n\mid m$, cioè possiamo dire che si possono togliere tutti gli 0 in fondo ed avere comunque un multiplo di $n$, ovvero $n\mid a_{i-j}$.

[Gerald Lambeau]

Bella soluzione, come sempre!

Testo nascosto:

Non è però quella a cui alludevo io, anche perché io l'ho risolto con una soluzione malatissima basata sui numeri con la virgola e periodo e la loro rappresentazione in frazione (e sono anche riuscito a spiegarla a un mio compagno di classe XD).

[Salvador]

In effetti grazie a Eulero per ogni $n$ coprimo con 10 il numero $\dfrac{10^{\phi(n)}-1}{9}$ gode di questa proprietà.