Dimostrare che $n|a_n$ con una definizione strana di $a_n$

[dario2994]

Dato $k\ge 0$ intero sia $a_i$ la sequenza di interi definita da $\displaystyle \sum_{d|n}a_d=k^n $.
Dimostrate che $n|a_n$

p.s. IMO shortlist 1989 problema 11 generalizzato
p.p.s. non particolarmente bello... ma ci sono 2 soluzioni almeno, equivalentemente istruttive

[Sonner]

Bon proviamoci, non sono troppo convinto

Sia $\mu (n)$ una funzione che vale $1$ se $n$ è libero da quadrati e ha un numero pari di fattori primi, $-1$ se è libero da quadrati e ha un numero dispari di fattori primi, $0$ se $n$ non è libero da quadrati. Allora se $f,g$ sono funzioni da Z in Z, vale questa formula (inversione di Mobius):

$$f(n)=\sum_{d\mid n} g(a) \iff g(n)=\sum_{d\mid n}f(\frac{n}{d})\mu (d)$$.

Per prima cosa dimostro che $\sum_{d\mid n} \mu (d)=0$ se $n>1$ mentre ovviamente per $\mu (1)=1$. Sia $n=\prod_{i=1}^k p_i^{\alpha_i}$: considero tutti i termini non nulli (quelli liberi da quadrati), di questi ce n'è 1 con 0 fattori, $k$ ne hanno 1, $k\choose i$ ne hanno i, ma $1-p+{p\choose 2}-\dots \pm {p\choose p}=(1-1)^p=0$ (@dario2994, finalmente questa idea sembra avere un senso ).

Adesso la parte davvero buffa:

$$f(n)=\sum_{d\mid n} g(a) \Rightarrow \sum_{ij=n}f(i)\mu (j)=\sum_{ij=n}\mu (j)\sum_{h\mid i} g(h)=\sum_{ij\mid n}g(i)\mu (j)=\sum_{ij=n} g(i)\sum_{h\mid j}\mu (h)=g(n)$$

Dove l'ultimo passaggio è proprio perchè $\sum_{h\mid j} \mu (h)=0$ tranne che per $j=1$ e quindi $i=n$.

Passiamo al problema: $a_n=\sum_{d\mid n}k^{\frac{n}{d}}\mu (d)$. Non resta che dimostrare $\sum_{d\mid n}k^{\frac{n}{d}}\mu (d) \equiv 0 \pmod n$. Prendo $p$ tale che $p^\alpha \mid\mid n$ e dimostro che $p^\alpha \mid a_n$. Osservo che per avere $\mu (d)$ non nullo è necessario che $p^2\nmid n$. Allora divido i divisori che soddisfano in due insiemi: multipli di $p$ e non-multipli di $p$. Se $t$ appartiene al primo insieme allora $pt$ appartiene al secondo, viceversa se $s$ appartiene al secondo insieme allora $p\mid\mid s$ e quindi $\frac{s}{p}$ appartiene al primo, quindi ho stabilito una bigezione tra ogni elemento del primo con ogni elemento del secondo. Inoltre ovviamente $\mu (t) =-\mu (pt)$, quindi posso scrivere la somma come $\sum_{t\mid n} (k^{\frac{n}{t}} - k^{\frac{n}{pt}})\mu (t)\equiv 0 \pmod {p^\alpha}$ perchè per Fermat lo è ogni addendo.

[dario2994]

Alrait
E vorrei sottolineare una cosa, sperando che la leggano più persone possibili... nonostante non lo abbia scritto il tizio qui sopra si è ricavato DA SOLO la formula d'inversione di mobius con una paginata di conti senza manco conoscere la formula di mobius (cioè $\mu(x)$) Stima e rispetto per ciò

[bĕlcōlŏn]

E bravo Sonner
Visto che è stata tirata in ballo la formula di inversione di Möbius, metto qualche rilancio
Date due funzioni aritmetiche (con dominio = $\mathbb{N}$) $f(n)$ e $g(n)$ definisco convoluzione di $f$ e $g$ tale somma: $f\cdot g = \displaystyle\sum_{d|n} f(d)g\left(\dfrac{n}{d}\right)$.
1) Dimostrate $\cdot$ è commutativa, associativa e distributiva.
2) Dimostrate che se $f$ e $g$ sono moltiplicative (i.e. se $\forall a,b \in \mathbb{N}$ t.c. $\gcd(a,b)=1$ allora $f(ab)=f(a)f(b)$), allora $f\cdot g$ è ancora moltiplicativo.
3) Trovate l'elemento neutro, ovvero quella funzione t.c. $f \cdot h = f$.
4) La formula di inversione diventa: date due funzioni $f$ e $g$, allora $f=g \cdot 1 \Leftrightarrow g = \mu \cdot f$, dove $\mu$ è stata definita precedentemente. Dimostratela usando i risultati precedenti.
5) Un'identità famosa: dimostrate $\phi \cdot 1 = n$, dove $\phi(n)$ è la funzione di eulero che fornisce il numero di numeri minori di $n$ e coprimi con questo.

Se qualcuno sa qualcos'altro sulle convoluzioni, che metta altri rilanci

[Mist]

$$f(n)=\sum_{d\mid n} g(a) \Rightarrow \sum_{ij=n}f(i)\mu (j)=\sum_{ij=n}\mu (i)\sum_{h\mid j} g(k)=\sum_{ij\mid n}f(i)\mu (j)=\sum_{ij=n} f(i)\sum_{h\mid j}\mu (j)=g(n)$$

Ok, mi vergogno un po', ma devo ammettere che non ho capito quasi niente di quella catena di uguaglianze, in particolare non capisco se qui: $\displaystyle \sum_{ij=n}\mu (i)\sum_{h\mid j} g(k)=\sum_{ij\mid n}f(i)\mu (j)$ dove c'è un $\mid$ doveva esserci un uguale o se sono io che non sto capendo niente Qualcuno mi aiuta ?