[L02/03] $111 \dots 111$

Numeri interi, divisibilità, primalità, ed equazioni a valori interi.

[L02/03] $111 \dots 111$

Messaggioda Gerald Lambeau » 21/03/2016, 19:42

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...)
.
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: [L02/03] $111 \dots 111$

Messaggioda Rho33 » 23/03/2016, 15:01

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 :lol: )

$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 :lol:


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$ !
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: [L02/03] $111 \dots 111$

Messaggioda alexthirty » 23/03/2016, 15:08

La soluzione è giusta... Tra l'altro penso proprio che a gare come Cesenatico si possa dare per scontato Fermat e Eulero-Fermat
alexthirty
 
Messaggi: 79
Iscritto il: 27/11/2013, 14:49

Re: [L02/03] $111 \dots 111$

Messaggioda Gerald Lambeau » 23/03/2016, 15:28

Buona! Ora fatela con solo strumenti elementari.
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: [L02/03] $111 \dots 111$

Messaggioda Rho33 » 27/04/2016, 16:53

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$ .
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: [L02/03] $111 \dots 111$

Messaggioda Drago » 27/04/2016, 20:48

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}$.
Avatar utente
Drago
 
Messaggi: 1055
Iscritto il: 14/03/2013, 15:51

Re: [L02/03] $111 \dots 111$

Messaggioda Gerald Lambeau » 27/04/2016, 21:43

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).
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: [L02/03] $111 \dots 111$

Messaggioda Salvador » 13/04/2017, 12:21

In effetti grazie a Eulero per ogni $n$ coprimo con 10 il numero $\dfrac{10^{\phi(n)}-1}{9}$ gode di questa proprietà.
Salvador
 
Messaggi: 265
Iscritto il: 26/11/2016, 11:55


Torna a Teoria dei Numeri

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti