Mostrare che $ n|a_n $.
Una simpatica succesione
Una simpatica succesione
Sia definita la successione degli $ \{a_i\} $ tale che $ \sum_{d|n}{a_d}=2^n $.
Mostrare che $ n|a_n $.
Mostrare che $ n|a_n $.
The only goal of science is the honor of the human spirit.
Ponendo $ $n=1$ $, trovo che $ $a_1=2$ $.
Considero ora $ $n=p$ $ primo: $ $2^p=a_1+a_p=2+a_p$ $, quindi $ $a_p=2^p-2=2(2^{p-1}-1)\equiv 0\pmod p$ $ per il piccolo teorema di Fermat.
Considero adesso $ $n=p^\alpha$ $, con $ $p$ $ primo: $ $2^{p^\alpha}=a_1+a_p+a_{p^2}+\cdots +a_{p^\alpha}$ $, cioe` $ $a_{p^\alpha}=2^{p^\alpha}-(a_1+a_p+\cdots +a_{p^{\alpha-1}})$ $ quindi $ $a_{p^\alpha}=2^{p^\alpha}-2^{p^{\alpha-1}}=2^{p^{\alpha-1}}\left(2^{p^\alpha - p^{\alpha-1}}-1\right)$ $; poiche` $ $p^\alpha-p^{\alpha-1}=\phi(p^\alpha)$ $, abbiamo che $ $a_{p^\alpha}\equiv 0\pmod {p^\alpha}$ $, per il teorema di Euler-Fermat.
Ora dimostro per induzione che la tesi e` vera per ogni valore di $ $n$ $. La mia ipotesi induttiva e` che $ $\forall m: m|n \Rightarrow m|a_m$ $.
Pongo $ $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ $: allora per ipotesi $ $2^n=a_1+a_{p_1}+\cdots +a_{p_k}+\cdots +a_n$ $; da questa relazione esplicito $ $a_n$ $, e poi studio l'espressione modulo $ $p_1^{\alpha_1}$ $: trovo che $ $a_n\equiv2^n-\left(a_1+a_{p_1}+\cdots+a_{p_1^{\alpha_1-1}p_2^{\alpha_2}\cdots p^k^{\alpha_k}}\right)\pmod {p_1^{\alpha_1}}$ $, (mancano i termini in cui compare $ $p_1^{\alpha_1}$ $ al pedice, perche` sono divisibili per $ $p_1^{\alpha_1}$ $). La somma dei termini tra parentesi e` uguale a $ $2^{p_1^{\alpha_1-1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}}$ $, quindi $ $a_n=2^{p_1^{\alpha_1-1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}} \left(2^{p_1^{\alpha_1}\cdots p_k^{\alpha_k}-p_1^{\alpha_1-1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}}-1\right)$ $.
L'esponente del primo termine tra parentesi e` uguale a $ $p_2^{\alpha_2}\cdots p_k^{\alpha_k} \left(p_1^{\alpha_1}-p_1^{\alpha_1-1}\right)$ $: poiche` il secondo termine e` $ $\phi(p_1^{\alpha_1})$ $, $ $a_n\equiv 0\pmod {p_1^{\alpha_1}}$ $. Chiaramente questo procedimento puo` essere applicato a qualunque fattore primo, quindi deve essere $ $a_n\equiv 0\pmod n$ $
Penso che ci sia qualcosa che non va nel passo induttivo.. qualcuno potrebbe dargli un'occhiata perfavore?
Ops: avevo scritto $ $a_1=1$ $, scusate l'errore di battitura..
Considero ora $ $n=p$ $ primo: $ $2^p=a_1+a_p=2+a_p$ $, quindi $ $a_p=2^p-2=2(2^{p-1}-1)\equiv 0\pmod p$ $ per il piccolo teorema di Fermat.
Considero adesso $ $n=p^\alpha$ $, con $ $p$ $ primo: $ $2^{p^\alpha}=a_1+a_p+a_{p^2}+\cdots +a_{p^\alpha}$ $, cioe` $ $a_{p^\alpha}=2^{p^\alpha}-(a_1+a_p+\cdots +a_{p^{\alpha-1}})$ $ quindi $ $a_{p^\alpha}=2^{p^\alpha}-2^{p^{\alpha-1}}=2^{p^{\alpha-1}}\left(2^{p^\alpha - p^{\alpha-1}}-1\right)$ $; poiche` $ $p^\alpha-p^{\alpha-1}=\phi(p^\alpha)$ $, abbiamo che $ $a_{p^\alpha}\equiv 0\pmod {p^\alpha}$ $, per il teorema di Euler-Fermat.
Ora dimostro per induzione che la tesi e` vera per ogni valore di $ $n$ $. La mia ipotesi induttiva e` che $ $\forall m: m|n \Rightarrow m|a_m$ $.
Pongo $ $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ $: allora per ipotesi $ $2^n=a_1+a_{p_1}+\cdots +a_{p_k}+\cdots +a_n$ $; da questa relazione esplicito $ $a_n$ $, e poi studio l'espressione modulo $ $p_1^{\alpha_1}$ $: trovo che $ $a_n\equiv2^n-\left(a_1+a_{p_1}+\cdots+a_{p_1^{\alpha_1-1}p_2^{\alpha_2}\cdots p^k^{\alpha_k}}\right)\pmod {p_1^{\alpha_1}}$ $, (mancano i termini in cui compare $ $p_1^{\alpha_1}$ $ al pedice, perche` sono divisibili per $ $p_1^{\alpha_1}$ $). La somma dei termini tra parentesi e` uguale a $ $2^{p_1^{\alpha_1-1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}}$ $, quindi $ $a_n=2^{p_1^{\alpha_1-1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}} \left(2^{p_1^{\alpha_1}\cdots p_k^{\alpha_k}-p_1^{\alpha_1-1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}}-1\right)$ $.
L'esponente del primo termine tra parentesi e` uguale a $ $p_2^{\alpha_2}\cdots p_k^{\alpha_k} \left(p_1^{\alpha_1}-p_1^{\alpha_1-1}\right)$ $: poiche` il secondo termine e` $ $\phi(p_1^{\alpha_1})$ $, $ $a_n\equiv 0\pmod {p_1^{\alpha_1}}$ $. Chiaramente questo procedimento puo` essere applicato a qualunque fattore primo, quindi deve essere $ $a_n\equiv 0\pmod n$ $
Penso che ci sia qualcosa che non va nel passo induttivo.. qualcuno potrebbe dargli un'occhiata perfavore?
Ops: avevo scritto $ $a_1=1$ $, scusate l'errore di battitura..
Nel frattempo che stefanos risponde..
$ a_i $ puo essere considerato come il numero di numeri in rappresentazione binaria che non contiene nessun sottogruppo di lunghezza $ j|i $ che si ripete dall'inizio alla fine di $ a_i $.
Il fatto che $ i|a_i $ segue dal fatto che è possibile permutare ciclicamente ogni $ a_i $ esattamente $ i $ volte.
$ a_i $ puo essere considerato come il numero di numeri in rappresentazione binaria che non contiene nessun sottogruppo di lunghezza $ j|i $ che si ripete dall'inizio alla fine di $ a_i $.
Il fatto che $ i|a_i $ segue dal fatto che è possibile permutare ciclicamente ogni $ a_i $ esattamente $ i $ volte.
The only goal of science is the honor of the human spirit.
Leggermente OT, ma.. Quel simbolo vuol dire "divisibile per"?jordan ha scritto:$ i|a_i $
Musica est exercitium aritmeticae occultum nescientis se numerari animi. (Leibniz)
La matematica può essere definita come la scienza in cui non sappiamo mai di che cosa stiamo parlando, né se ciò che diciamo è vero. (B. Russell)
La matematica può essere definita come la scienza in cui non sappiamo mai di che cosa stiamo parlando, né se ciò che diciamo è vero. (B. Russell)
.Intendevo dire questo: procedo per induzione; suppongo che per tutti i numeri $ $m<n$ $ valga che $ $m|a_m$ $: in particolare, se $ $m|n$ $, allora m|a_m. Nel pezzo che hai citato, applico l'ipotesi induttiva ai termini $ $a_i$ $ in cui $ $p_1^{\alpha_1}$ $ divide $ $i$ $, che sono quindi congrui a $ $0$ $ modulo $ $p_1^{\alpha_1}$ $. Spero di essere stato chiaro (ma non sono certo che sia un procedimento corretto 
)
)