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