Sia [tex]\displaystyle n[/tex] un numero intero positivo.
1. Dimostrare che per ogni [tex]\displaystyle n[/tex] esiste un numero [tex]\displaystyle m[/tex] della forma [tex]m=\displaystyle \underbrace{111...11}_{\text{x volte 1}} \underbrace{00...00}_{\text{y volte 0}}[/tex] (in pratica, un po' di uni seguiti da un po' di zeri, in base 10, naturalmente) tale che [tex]\displaystyle n | m[/tex].
2. Per ogni [tex]\displaystyle n[/tex] trovare il più piccolo [tex]\displaystyle m[/tex], sempre della stessa forma, tale che [tex]\displaystyle n|m[/tex].
3. E se il numero [tex]\displaystyle m[/tex] fosse della forma [tex]m=\displaystyle \underbrace{kkk...kk}_{\text{x volte k}} \underbrace{00...00}_{\text{y volte 0}}[/tex][tex]\displaystyle [/tex] con [tex]\displaystyle 1<k<10[/tex] intero?
n|111...000
-
paga92aren
- Messaggi: 358
- Iscritto il: 31 lug 2010, 10:35
Re: n|111...000
a) Riscrivo il numero $m=\frac{10^x-1}{9}10^y$ devo dimostrare che per ogni $n$ esistono $x$ e $y$ tali che $n|\frac{10^x-1}{9}10^y$
Se $(10,n)=1$ allora pongo $10^x\equiv 1 \mod 9n$ uso il piccolo teorema di Fermat e pongo $x=\phi(9n)$ e ho vinto!
Se $(10,n)\not=1$ allora impongo $y=\max\{v_2(n), v_5(n)\}$ e detto $n'=\frac{n}{v_2(n)v_5(n)}$ scelgo $x=\phi(9n')$
In entrambi i casi ho trovato $x,y$ adatti.
b) scelti così $x,y$ non si può scegliere un $y$ minore perché 2 e 5 non dividono il primo termine e almeno uno dei due non divide neanche $10^{y-k}$.
Invece esistono $x$ minori perché la funzione $\phi$ non implica che l'esponente sia il più piccolo possibile: es $2^6\equiv1 \mod7$ ma anche $2^3\equiv1\mod7$
c) esiste comunque un multiplo di $n$ della forma $k\frac{10^x-1}{9}10^y$ ma rimane il problema del punto b) che devo ancora pensarci.
EDIT: avevo dimenticato un 9
Se $(10,n)=1$ allora pongo $10^x\equiv 1 \mod 9n$ uso il piccolo teorema di Fermat e pongo $x=\phi(9n)$ e ho vinto!
Se $(10,n)\not=1$ allora impongo $y=\max\{v_2(n), v_5(n)\}$ e detto $n'=\frac{n}{v_2(n)v_5(n)}$ scelgo $x=\phi(9n')$
In entrambi i casi ho trovato $x,y$ adatti.
b) scelti così $x,y$ non si può scegliere un $y$ minore perché 2 e 5 non dividono il primo termine e almeno uno dei due non divide neanche $10^{y-k}$.
Invece esistono $x$ minori perché la funzione $\phi$ non implica che l'esponente sia il più piccolo possibile: es $2^6\equiv1 \mod7$ ma anche $2^3\equiv1\mod7$
c) esiste comunque un multiplo di $n$ della forma $k\frac{10^x-1}{9}10^y$ ma rimane il problema del punto b) che devo ancora pensarci.
EDIT: avevo dimenticato un 9
Re: n|111...000
overkill!paga92aren ha scritto:a) Riscrivo il numero $m=\frac{10^x-1}{9}10^y$ devo dimostrare che per ogni $n$ esistono $x$ e $y$ tali che $n|\frac{10^x-1}{9}10^y$
Se $(10,n)=1$ allora pongo $10^x\equiv 1 \mod 9n$ uso il piccolo teorema di Fermat e pongo $x=\phi(9n)$ e ho vinto!
Se $(10,n)\not=1$ allora impongo $y=\max\{v_2(n), v_5(n)\}$ e detto $n'=\frac{n}{v_2(n)v_5(n)}$ scelgo $x=\phi(9n')$
In entrambi i casi ho trovato $x,y$ adatti.
Testo nascosto:
be', questa non mi sembra una rispostapaga92aren ha scritto:b) scelti così $x,y$ non si può scegliere un $y$ minore perché 2 e 5 non dividono il primo termine e almeno uno dei due non divide neanche $10^{y-k}$.
Invece esistono $x$ minori perché la funzione $\phi$ non implica che l'esponente sia il più piccolo possibile: es $2^6\equiv1 \mod7$ ma anche $2^3\equiv1\mod7$
Testo nascosto:
Re: n|111...000
$ m=\displaystyle 10^{\text{max}\{\upsilon_2(n),\upsilon_5(n)\}}\cdot \left(\frac{10^{\text{lcm}\{\text{ord}_2(2^{-\upsilon_2(n)}5^{-\upsilon_5(n)}n),\text{ord}_5(2^{-\upsilon_2(n)}5^{-\upsilon_5(n)}n)\}}-1}{9}\right) $ngshya ha scritto:2. Per ogni $ \displaystyle n $ trovare il più piccolo $ \displaystyle m $, sempre della stessa forma, tale che $ \displaystyle n|m $.
Ultima modifica di jordan il 03 gen 2011, 02:06, modificato 1 volta in totale.
The only goal of science is the honor of the human spirit.
Re: n|111...000
suppongo sia un ${\rm ord}_{10}$ all'esponente, al posto di un ${\rm ord}_2$ (e comunque io scriverei ${\rm ord}_a(b)$ per dire l'ordine moltiplicativo di $b$ mod $a$, e non viceversa: non so quanto sia universale questa convenzione, ma di solito si capisce dal contesto).
Re: n|111...000
Ciaoma_go ha scritto:suppongo sia un ${\rm ord}_{10}$ all'esponente, al posto di un ${\rm ord}_2$ (e comunque io scriverei ${\rm ord}_a(b)$ per dire l'ordine moltiplicativo di $b$ mod $a$, e non viceversa: non so quanto sia universale questa convenzione, ma di solito si capisce dal contesto).
Si, volevo intendere il minimo comune multiplo tra ord_2(N) e ord_5(N), dove N è composto dai soli fattori di n coprimi con 10.. (quando ho fatto copia mi sono dimenticato di mettere il 5, edito subito).
The only goal of science is the honor of the human spirit.
Re: n|111...000
Ogni riferimento al TdN 1 dell'ammissione al WC è puramente casuale ...
Glory is like a circle in the water,
Which never ceaseth to enlarge itself,
Till by broad spreading it disperses to naught.
Which never ceaseth to enlarge itself,
Till by broad spreading it disperses to naught.
Re: n|111...000
Davvero è un esercizio dell'ammissione al WC? 
The only goal of science is the honor of the human spirit.
Re: n|111...000
Di simile hanno solo dei numeri definiti in modo simile e delle relazioni di divisibilità. I punti in comune si fermano lì: questo problema ce l'hanno proposto al progetto Diderot, anche prima che uscissero gli esercizi di ammissione al WC se non sbaglio (chiedo conferma a ngshya).Xamog ha scritto:Ogni riferimento al TdN 1 dell'ammissione al WC è puramente casuale ...
io pensavo che per essere ammessi al WC bastasse la solita monetina da 20 centesimi :p
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
Re: n|111...000
Credo che quelli del Diderot lo abbiano preso da qualche altra parte... e forse è anche un fatto noto.
jordan è tornato!
jordan è tornato!