Siano $a$ e $n$ interi positivi. Mostrare che
\[\sum_{i=1}^n a^{(i,n)}\]
è multiplo di $n$; dove $(i,n)$ è il massimo comun divisore tra $i$ ed $n$.
Re: Brucialato
Inviato: 07 gen 2018, 17:39
da Salvador
Testo nascosto:
Sia $f(a,n) = \sum_{i=1}^{n}{a^{(i,n)}}$.
Chiaramente $(i,n)$ è un divisore di $n$. Se $d | n$, vi sono $\phi(\frac{n}{d})$ interi compresi fra 1 ed $n$ il cui GCD con $n$ è esattamente $d$ : infatti questi sono esattamente quanti i numeri compresi fra $1$ ed $\frac{n}{d}$ coprimi con $\frac{n}{d}$, ovvero $\phi(\frac{n}{d})$. Per ognuno di questi si ha $a^(i,n) = a^d$, pertanto:
$$f(a,n) = \sum_{d | n}{\phi(\frac{n}{d})a^d} = \sum_{d | n}{\phi(d)a^{\frac{n}{d}}}$$
Dimostriamo ora per induzione che se $n=p^k$, con $p$ primo e $k \geq 1$ la tesi è vera.
Per $k=1$ si ha $f(a,p)=\phi(1)a^p + \phi(p-1)a = a^p+(p-1)a \equiv a^p - a \equiv 0 \pmod{p}$.
Supponiamo ora la tesi vera per $p^{k-1}$. Abbiamo:
$f(a,p^k) = \phi(1)a^{p^k} + \phi(p)a^{p^{k-1}} + ... + \phi(p^k)a \equiv a^{p^{k-1}} + (p-1)a^{p^{k-1}} + ... + \sum_{i=2}^{k}{\phi(p^i)a^{p^{k-i}}} \equiv pa^{p^{k-1}} + \sum_{i=2}^{k}{p^{i-1}(p-1)a^{p^{k-i}}} \equiv p f(a,p^{k-1}) \equiv 0 \pmod{p^k}$,
poiché per ipotesi induttiva $f(a,p^{k-1}) \equiv 0 \pmod{p^{k-1}}$.
Adesso consideriamo $n$ qualsiasi e sia $p$ un primo che divide $n$ e $k=v_p(n)$.
Osserviamo ora che per ogni divisore $d$ di $\frac{n}{p^k}$, $dp^i, 0 \leq i \leq k$ è un divisore di $n$ e per ogni divisore $b$ di $n$ con $0 \leq v_p(b) \leq k$, $\frac{b}{p^v_p(b)}$ è un divisore di $\frac{n}{p^k}$: pertanto possiamo raggruppare i divisori di $n$ in $\sigma\left(\frac{n}{p^k}\right)$ insiemi, in modo che per ogni divisore $d$ di $\frac{n}{p^k}$ esista esattamente un insieme che contiene tutti i divisori di $n$ della forma $dp^i, 0 \leq i \leq k$.