Zeri e Uni

[axpgn]

Sia $n$ un numero naturale.
Dimostrare che $n$ ha un multiplo (diverso da zero) la cui rappresentazione in base dieci contenga solo Zeri e Uni.

Cordialmente, Alex

[killing_buddha]

I numeri sono polinomi nella variabile formale "10".

Se $n=\sum_{i=0}^p a_i 10^i$ e $k = \sum_{j=0}^q b_j 10^j$ il loro prodotto è
\[
nk = \sum_{l=0}^{p+q} \left(\sum_{s+t=l}a_s b_t\right) 10^l
\]Tu stai chiedendo di trovare certi $b_t$ per cui il sistema
\[
\begin{cases}
a_0b_0 \in \{0,1\}\\
a_0b_1 + a_1b_0 \in \{0,1\}\\
\vdots\\
\end{cases}
\] fino al grado di $nk$. Questo, evidentemente, innesca un processo di soluzione induttiva che termina (perché $n,k$ hanno grado finito): a seconda di chi sia $a_0$ si determina un (non unico) $b_0$, che a sua volta determina $b_1$.. e siccome il sistema in questione è sempre lineare nei coefficienti $a_i$, si risolverà nelle $b_j$.

[dan952]

Preso $n$ non multiplo di 2 e di 5, applicando il teorema di Eulero (quello di aritmetica modulare) si ha che il numero che soddisfa la richiesta è
$\sum_{i=0}^{n-1} 10^{i\varphi(n)}$
dove $\varphi(n)$ è la funzione di Eulero.

I casi multiplo di 5 e di 2 si procede nel seguente modo: si divide $n$ per $2^{a}5^{b}$, dove $a$ e $b$ sono gli esponenti massimi di questi fattori primi, ora quel che rimane è $n/(2^{a}5^{b})=k$ che sappiamo avere un multiplo di quel tipo $m=\sum_{i=0}^{k-1} 10^{i\varphi(k)}$ come richiesto, a questo punto rimoltiplichiamo $m$ per $10^{\text{max}(a,b)}$, e abbiamo concluso.

[axpgn]

"Non capisco ma mi adeguo" (cit.)

@kb

Penso di aver afferrato il concetto (forse ... ) ma ho dei dubbi .. per esempio, il sistema mi pare impreciso, nel senso che il risultato di quelle espressioni potrebbe non rientrare in quel range ma essere accettabile (p.es. $10, 21$) e poi mancano gli eventuali riporti ... ma oltre a questo come fai ad affermare che quel sistema sia sempre compatibile o che la soluzione sia diversa da tutti zeri?

[ot]Metti sotto spoiler le tue idee[/ot]

@dan95

Dovresti esplicitare come giungi a quella scrittura, io non ci riesco ...

Cordialmente, Alex

[dan952]

Per ogni $0 \leq i < n$ si ha (teorema di Eulero) $10^{i\varphi(n)} \equiv 1 \mod n$, sommando su $i$ si ottiene $\sum_{i=0}^{n-1} 10^{i\varphi(n)} \equiv n \mod n$

[veciorik]

Prendiamo ad esempio n=7.
Proviamo le tecniche indicate.
Possono trovare il minimo m tale che 7m sia una sequenza di soli 1 e 0, in base 10 ?
Credo che il minimo sia:

$143=1001/7$

[axpgn]

Ok, dan95, ho capito ... Bella dimostrazione

In pratica ...

Dato $n$, il multiplo in questione si costruisce inserendo $n$ cifre $1$ distanziate fra loro di $phi(n)$ posizioni.

La mia è questa ...

Sia $n$ un numero naturale e sia dato l'insieme $A={1, 11, 111, ...}$ composto da $n+1$ elementi e il cui massimo sia composto da $n+1$ cifre $1$.
Dato che $n$ ha $n$ resti modulo $n$, due elementi di $A$ hanno lo stesso resto: la loro differenza è il numero cercato.

Cordialmente, Alex