Multiplo 111000

[dr00ster]

Problema che mi era stato posto un po' di tempo fa al progetto Diderot (conoscete?):

Dimostrare che ogni numero naturale ha un multiplo scrivibile come una successione di \(\displaystyle 1 \) seguita da una successione di \(\displaystyle 0 \) (anche nulla).

È più facile capire con degli esempi:
Scegliendo come numero \(\displaystyle 9 \), questo ha come multiplo \(\displaystyle 111111111 \) (successione di \(\displaystyle 1 \) seguita da successione di \(\displaystyle 0 \) nulla).
Se scelgo come numero \(\displaystyle 4 \), questo ha come multiplo \(\displaystyle 100 \).
Dimostrare che ciò è valido per qualsiasi numero naturale \(\displaystyle n \).

[Sk_Anonymous]

Se non fraintendo o ricordo male, mi pare che un problema parente stretto di questo sia stato trattato anche qui, qualche tempo fa.
Dovrebbe essere uno dei vecchi problemi SNS.

[orsoulx]

Sia $ n $ il numero dato. Fra $ 9n+1 $ potenze successive di $ 10 $, ne esisteranno, per il principio dei cassetti, almeno $ 2 $ diverse che danno il medesimo resto nella divisione per $ 9n $. La differenza fra la maggiore e la minore di queste, divisa per $ 9 $, è uno dei multipli di $ n $ della forma cercata.

Ciao
B.

[dan952]

Sono ripetitivo...
Per le potenze di 2 e 5 stiamo apposto, infatti $2^n ||10^n$ e $5^n||10^n$, ci resta da vedere che succede con il teorema di Eulero per i casi $n$ tale che $(10,n)=1$ e $(9,n)=1$ e $n=3^m$ con $m>2$.
Vediamo il primo caso: Da Eulero sappiamo che $10^{\phi(n)} -=1\mod n$ quindi $10^{\phi(n)}-1=nk=9\cdot 1111...1$ poiché $(9,n)=1$ segue la tesi.
Il caso $3^m$ con $m>2$ si risolve in modo analogo.

[dr00ster]

Ok, chiedo scusa per la risposta un po' in ritardo ma stavo rileggendo il post e mi è sorto un dubbio...

"dan95":Il caso \(\displaystyle 3^m \) con \(\displaystyle m>2 \) si risolve in modo analogo.

Nel caso \(\displaystyle n=3^m \), $ 10^(varphi(n))-1=9*111...1$ ma non è più valido $ (9,n)=1 $. Come dimostro che $ 3^n $ divide 111...1?

Grazie mille!

[dan952]

Poiché $m>2$ si ha $(10^{\phi(n)}-1)/3^m=\frac{111....11}{3^{m-2}}$ la tesi segue dal fatto che $3^m| 10^{\phi(n)}-1$.

[dr00ster]

Scusami, dubbio stupido! Chiarissimo

[orsoulx]

Effettivamente, cacciare le zanzare con la fionda è attività lecita e richiede una certa abilità.
Ciao
B.