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.
Re: Successione multipla degli indici
Inviato: 12 nov 2017, 19:32
da Ventu06
Testo nascosto:
Caso $n=1$: $a_1$ è intero, quindi $1$ è un suo divisore.
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:
- 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:
Dato che, se $p_1^{e_1} \mid n$, allora $p_1^{e_1} \mid a_n$, abbiamo che $n \mid a_n$.
Re: Successione multipla degli indici
Inviato: 12 nov 2017, 21:22
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.
Re: Successione multipla degli indici
Inviato: 19 nov 2017, 22:54
da Troleito br00tal
Problema apparentemente poco correlato:
quanti sono i polinomi monici irriducibili su $\mathbb{F_p}$ di grado $n$?
Re: Successione multipla degli indici
Inviato: 24 dic 2017, 15:25
da Salvador
Insomma è una generalizzazione del piccolo teorema di Fermat.