Successione multipla degli indici

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Successione multipla degli indici

Messaggio da Gerald Lambeau »

Sia $a_1, a_2, \dots$ una successione infinita di interi tali che
$\displaystyle 2^n = \sum_{d \mid n} a_d$ per ogni $n$ intero positivo.
Dimostrare che $n \mid a_n$ per ogni $n$ intero positivo.
"If only I could be so grossly incandescent!"
Ventu06
Messaggi: 15
Iscritto il: 15 apr 2016, 21:27
Località: Provincia di Ancona

Re: Successione multipla degli indici

Messaggio da Ventu06 »

Testo nascosto:

Caso $n=1$: $a_1$ è intero, quindi $1$ è un suo divisore.

Altrimenti scomponiamo $n$ in fattori primi: $n=p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}$ ; poniamo $m=2^{p_1^{e_1-1} p_2^{e_2-1} \dots p_k^{e_k-1}}$

Attraverso la formula di inversione di Mobius troviamo che $a_n = \sum\limits_{d \mid n} \mu \left( \dfrac{n}{d} \right) 2^d$ , dove $\mu (n)$ è la funzione di Mobius.
Sviluppando i conti abbiamo:

$a_n = \sum\limits_{d \mid n} \mu \left( \dfrac{n}{d} \right) 2^d =$

$\mu(1) 2^{p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}}
+ \left( \mu(p_1) 2^{p_1^{e_1-1} p_2^{e_2} \dots p_k^{e_k}} + \mu(p_2) 2^{p_1^{e_1} p_2^{e_2-1} \dots p_k^{e_k}} + \dots + \mu(p_k) 2^{p_1^{e_1} p_2^{e_2} \dots p_k^{e_k-1}} \right)
+ \dots
+ \mu(p_1 p_2 \dots p_k) 2^{p_1^{e_1-1} p_2^{e_2-1} \dots p_k^{e_k-1}} =$

$m^{p_1 p_2 \dots p_k}
- ( m^{p_2 p_3 \dots p_{k}} + m^{p_1 p_3 \dots p_k}+ \dots +m^{p_1 p_2 \dots p_{k-1}} )
+ \dots
(-1)^km$


Dimostriamo ora che ogni potenza di ogni primo che divide $n$, ad esempio $p_1^{e_1}$, divide $a_n$.

Raccogliamo i termini nel seguente modo:

$m^{p_1 p_2 \dots p_k} -
( m^{p_2 p_3 \dots p_{k}} + m^{p_1 p_3 \dots p_k}+ \dots +m^{p_1 p_2 \dots p_{k-1}} )+
\dots (-1)^km =$

$(m^{p_1 p_2 \dots p_k} - m^{p_2 p_3 \dots p_{k}})
- ( (m^{p_1 p_3 \dots p_k} - m^{p_3 \dots p_k}) + \dots + (m^{p_1 p_2 \dots p_{k-1}} - m^{p_2 \dots p_{k-1}}) )
+ \dots
(-1)^{k-1}(m^{p_1}-m) =$

$m^{p_2 p_3 \dots p_{k}}(m^{(p_1-1)p_2 p_3 \dots p_{k}}-1)
- ( m^{p_3 \dots p_k}(m^{(p_1-1)p_3 \dots p_k}-1) + \dots + m^{p_2 \dots p_{k-1}}(m^{(p_1-1)p_2 \dots p_{k-1}}-1) )
+ \dots
(-1)^{k-1} m(m^{(p_1-1)}-1)$

Possiamo quindi esprimere $a_n$ come somma di termini del tipo

$m^r(m^{(p_1-1)r}-1)=$

$m^r \left( 2^{(p_1^{e_1-1} p_2^{e_2-1} \dots p_k^{e_k-1})(p_1-1)r} -1 \right) =$

$m^r \left( \left( 2^{p_1^{e_1-1}(p_1-1)} \right) ^{(p_2^{e_2-1} \dots p_k^{e_k-1})r} -1 \right) =$

$m^r \left( \left( 2^{\varphi(p_1^{e_1})} \right) ^{(p_2^{e_2-1} \dots p_k^{e_k-1})r} -1 \right)$


Distinguiamo due casi:

- Se $p_1=2$, abbiamo che $2^{e_1} \mid m^r = 2^{2^{e_1-1} p_2^{e_2-1} \dots p_k^{e_k-1} r}$ se $e_1 \le 2^{e_1-1})$
Ma $2^{e_1-1}=(1+1)^{e_1-1}=1{e_1-1 \choose 0}+1{e_1-1 \choose 1}+ \dots \ge 1+ (e_1-1) =e_1$, quindi la disuguaglianza è vera.
Dato che $m^r$ è un fattore presente in ogni termine, $2^{e_1}$ divide $a_n$.

- Se $p_1 \neq 2$, possiamo concludere grazie al teorema di Eulero:

$a_n = m^r \left( \left( 2^{\varphi(p_1^{e_1})}\right) ^{(p_2^{e_2-1} \dots p_k^{e_k-1})r} -1 \right) \equiv
m^r \left( 1 ^{(p_2^{e_2-1} \dots p_k^{e_k-1})r} -1 \right) \equiv
m^r ( 1 -1 )\equiv
0 \pmod{p_1^{e_1}}$



Dato che, se $p_1^{e_1} \mid n$, allora $p_1^{e_1} \mid a_n$, abbiamo che $n \mid a_n$.

Ultima modifica di Ventu06 il 12 nov 2017, 22:58, modificato 1 volta in totale.
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: Successione multipla degli indici

Messaggio da Gerald Lambeau »

Ok, giusta :) .
In alternativa, senza scomodare Möbius, si può fare per induzione estesa su $n$; si raccolgono cose diverse, ma l'obiettivo è sempre lo stesso: ottenere la phi dei primi che compaiono elevati al massimo esponente insieme a roba multipla di quelle stesse potenze di primi.
"If only I could be so grossly incandescent!"
Avatar utente
Troleito br00tal
Messaggi: 683
Iscritto il: 16 mag 2012, 22:25

Re: Successione multipla degli indici

Messaggio da Troleito br00tal »

Problema apparentemente poco correlato:

quanti sono i polinomi monici irriducibili su $\mathbb{F_p}$ di grado $n$?
Salvador
Messaggi: 42
Iscritto il: 09 apr 2017, 14:35

Re: Successione multipla degli indici

Messaggio da Salvador »

Insomma è una generalizzazione del piccolo teorema di Fermat.
Rispondi