Divide... et impera!
Divide... et impera!
Problema #1: mostrare che, per ogni $ m\in\mathbb{N}_0 $, con $ m \neq 2 $, esistono infiniti $ n\in\mathbb{N}_0 $ tali che possa scriversi: $ \displaystyle{n = d_1 + d_2 + \ldots + d_m =: \sum_{k=1}^m d_k} $, ove $ d_1, d_2, \ldots, d_m $ sono divisori interi positivi distinti di $ n $. Provare quindi che questa stessa condizione non è mai soddisfatta là dove si ammetta $ m = 2 $.
Dimostriamo innanzitutto che, se esiste un certo $ n\in\mathbb{N}_0 $ che sia uguale alla somma di m suoi divisori distinti, allora esistono infiniti n che verificano questa proprietà.
In particolare verifichiamo che se n verifica le condizioni poste, allora esiste un $ n_1>n $ che le verifica.
Poniamo allora
$ n=d_1+d_2+\ldots+d_m $
Moltiplicando ambo i membri per
$ A = d_1*d_2*\ldots*d_m $
otteniamo:
$ A*n=A*d_1+A*d_2+\ldots+A*d_m $
Notiamo che gli m termini che compaiono nel membro di destra sono tutti divisori di A*n e che sono diversi tra loro,perchè i $ d_i $ sono distinti.
Inoltre, poichè A è sempre una quantità positiva, A*n è maggiore di n.
Il problema si riduce dunque a dimostrare che per ogni $ m\in\mathbb{N}_0 , $ con $ m\neq 2 $ esiste un n tale che sia uguale alla somma di m suoi divisori distinti.
Per m=1 la tesi è banale.
Per m=3, prendiamo n=6=1+2+3
Per m=4, prendiamo 2n=12=1+2+3+6
Per m=5, prendiamo 4n=24=1+2+3+6+12
Più in generale, dimostriamo che,posto m > 1, se n verifica la tesi per m, allora 2n verifica la tesi per m+1.
Poniamo come al solito:
$ n=d_1+d_2+\ldots+d_m $
Abbimo ora che
$ 2n=d_1+d_2+\ldots+d_m+n $
e poichè abbiamo supposto m>1, n non può essere uguale a nessuno dei $ d_i $.
Quindi, dato che per m = 3 abbiamo una soluzione, avremo una soluzione per tutti gli $ m>=3 $.
Ci resta ora de dimostrare che non esiste alcun $ n\in\mathbb{N}_0 $ che sia uguale alla somma di due suoi divisori distinti.
Se infatti poniamo $ n=d_1+d_2 $,dovremmo avere:
$ d_1|(d_1+d_2) $ e $ d_2|(d_1+d_2) $
cioè
$ d_1|d_2 $ e $ d_2|d_1 $
Ma questo avviene solo quando $ d_1=d_2 $.
Poichè per ipotesi i divisori devono essere distinti, per m = 2 non abbiamo soluzioni e questo conclude la dimostrazione.
In particolare verifichiamo che se n verifica le condizioni poste, allora esiste un $ n_1>n $ che le verifica.
Poniamo allora
$ n=d_1+d_2+\ldots+d_m $
Moltiplicando ambo i membri per
$ A = d_1*d_2*\ldots*d_m $
otteniamo:
$ A*n=A*d_1+A*d_2+\ldots+A*d_m $
Notiamo che gli m termini che compaiono nel membro di destra sono tutti divisori di A*n e che sono diversi tra loro,perchè i $ d_i $ sono distinti.
Inoltre, poichè A è sempre una quantità positiva, A*n è maggiore di n.
Il problema si riduce dunque a dimostrare che per ogni $ m\in\mathbb{N}_0 , $ con $ m\neq 2 $ esiste un n tale che sia uguale alla somma di m suoi divisori distinti.
Per m=1 la tesi è banale.
Per m=3, prendiamo n=6=1+2+3
Per m=4, prendiamo 2n=12=1+2+3+6
Per m=5, prendiamo 4n=24=1+2+3+6+12
Più in generale, dimostriamo che,posto m > 1, se n verifica la tesi per m, allora 2n verifica la tesi per m+1.
Poniamo come al solito:
$ n=d_1+d_2+\ldots+d_m $
Abbimo ora che
$ 2n=d_1+d_2+\ldots+d_m+n $
e poichè abbiamo supposto m>1, n non può essere uguale a nessuno dei $ d_i $.
Quindi, dato che per m = 3 abbiamo una soluzione, avremo una soluzione per tutti gli $ m>=3 $.
Ci resta ora de dimostrare che non esiste alcun $ n\in\mathbb{N}_0 $ che sia uguale alla somma di due suoi divisori distinti.
Se infatti poniamo $ n=d_1+d_2 $,dovremmo avere:
$ d_1|(d_1+d_2) $ e $ d_2|(d_1+d_2) $
cioè
$ d_1|d_2 $ e $ d_2|d_1 $
Ma questo avviene solo quando $ d_1=d_2 $.
Poichè per ipotesi i divisori devono essere distinti, per m = 2 non abbiamo soluzioni e questo conclude la dimostrazione.
sì, esattamente!
Una soluzione perfetta, Igor! Bene, non è il caso di adagiarsi sugli allori, passiamo avanti...
Problema #2: fissato $ n\in\mathbb{N}_0 $, determinare (dopo averne dimostrata l'esistenza) il minimo intero $ k \geq 2 $ tale che, comunque scelti $ p_1, p_2, \ldots, p_k\in\mathfrak{P} $, con $ p_1 < p_2 < \ldots < p_k $, esistano $ i, j = 1, 2, \ldots, k $, con $ i\neq j $, per cui $ n \mid (p_i - p_j) $.
Problema #2: fissato $ n\in\mathbb{N}_0 $, determinare (dopo averne dimostrata l'esistenza) il minimo intero $ k \geq 2 $ tale che, comunque scelti $ p_1, p_2, \ldots, p_k\in\mathfrak{P} $, con $ p_1 < p_2 < \ldots < p_k $, esistano $ i, j = 1, 2, \ldots, k $, con $ i\neq j $, per cui $ n \mid (p_i - p_j) $.
Supponiamo n > 1. Detto $ x $ il numero di fattori primi distinti che dividono $ n $, allora $ k = \varphi(n) + x + 1 $.
Chiamiamo $ A $ l'insieme dei numeri primi che dividono $ n $, e $ B $ l'insieme complementare, formato da tutti i primi che non dividono $ n $. Ovviamente $ |A| = x $. Inoltre tutti i primi appartenenti a $ b $ sono della forma $ kn + p $, dove$ k $ e $ p $ sono numeri naturali e $ p $ è primo con $ n $. Chiamiamo $ a_1 < a_2 < ... < a_{\varphi(n)} $ la successione ordinata dei numeri minori di $ n $ e primi con $ n $. Allora per il teorema di Dirichlet possiamo trovare $ k_1 $, $ k_2 $, ..., $ k_{\varphi(n)} $ tali che $ b_i = k_i \cdot n + a_i $, con $ 1 \leq i \leq \varphi(n) $. Se consideriamo l'insieme $ C $ formato dai numeri primi divisori di $ n $ e da $ b_1 $, $ b_2 $, ..., $ b_{\varphi(n)} $, notiamo che tutti gli elementi di questo insieme sono distinti modulo $ n $, pertanto la differenza tra due qualsiasi elementi non può essere divisibile per $ n $. Questo dimostra che $ k > |C| = \varphi(n) + x $.
Viceversa, qualunque insieme $ D $ contenente almeno $ \varphi(n) + x + 1 $ numeri primi, può avere al massimo $ x $ numeri primi appartenenti ad $ A $ e almeno $ \varphi(n) + 1 $ in $ B $. Dal momento che i numeri primi in $ B $ possono essere congrui modulo $ n $ solo $ \varphi(n) $ valori diversi, per il pigeonhole ci sono due primi congrui tra loro modulo $ n $. Quindi $ k <= \varphi(n) + x + 1 $, che unita al risultato precedente dimostra la tesi.
Chiamiamo $ A $ l'insieme dei numeri primi che dividono $ n $, e $ B $ l'insieme complementare, formato da tutti i primi che non dividono $ n $. Ovviamente $ |A| = x $. Inoltre tutti i primi appartenenti a $ b $ sono della forma $ kn + p $, dove$ k $ e $ p $ sono numeri naturali e $ p $ è primo con $ n $. Chiamiamo $ a_1 < a_2 < ... < a_{\varphi(n)} $ la successione ordinata dei numeri minori di $ n $ e primi con $ n $. Allora per il teorema di Dirichlet possiamo trovare $ k_1 $, $ k_2 $, ..., $ k_{\varphi(n)} $ tali che $ b_i = k_i \cdot n + a_i $, con $ 1 \leq i \leq \varphi(n) $. Se consideriamo l'insieme $ C $ formato dai numeri primi divisori di $ n $ e da $ b_1 $, $ b_2 $, ..., $ b_{\varphi(n)} $, notiamo che tutti gli elementi di questo insieme sono distinti modulo $ n $, pertanto la differenza tra due qualsiasi elementi non può essere divisibile per $ n $. Questo dimostra che $ k > |C| = \varphi(n) + x $.
Viceversa, qualunque insieme $ D $ contenente almeno $ \varphi(n) + x + 1 $ numeri primi, può avere al massimo $ x $ numeri primi appartenenti ad $ A $ e almeno $ \varphi(n) + 1 $ in $ B $. Dal momento che i numeri primi in $ B $ possono essere congrui modulo $ n $ solo $ \varphi(n) $ valori diversi, per il pigeonhole ci sono due primi congrui tra loro modulo $ n $. Quindi $ k <= \varphi(n) + x + 1 $, che unita al risultato precedente dimostra la tesi.
...o più sboroneamente $ k = \varphi(n) + \omega(n) + 1 $, utilizzando la definizione di una certa funzione aritmetica che mi sono giusto permesso di introdurre ufficialmente da qualche parte, lì fra le pagine del glossario...Spider ha scritto:Supponiamo n > 1. Detto $ x $ il numero di fattori primi distinti che dividono $ n $, allora $ k = \varphi(n) + x + 1 $.
Hai usato dell'inchiostro simpatico o nel tuo discorso mancava effettivamente qualcosina?!?Spider ha scritto:[...] Allora per il teorema di Dirichlet possiamo trovare $ k_1 $, $ k_2 $, ..., $ k_{\varphi(n)} $ tali che $ b_i = k_i \cdot n + a_i $ sia un numero primo naturale, con $ 1 \leq i \leq \varphi(n) $.
E a parte questo, nota come la relazione da te stabilita continui ad essere valida pure in riferimento al caso $ n = 1 $, essendo $ \varphi(1) = 1 $ ed $ \omega(1) = 0 $.eDHiT: trovo che la tua soluzione sia davvero esemplare, Spaiderino caro! Del resto, c'era da aspettarselo...
