Bel probbo ggwp

[Fenu]

Per ogni intero $n\geq 2$, sia $f(n)$ la funzione che calcola la somma degli interi positivi $\leq n$ che non sono coprimi con $n$. Dimostrare che $f(n+p)\neq f(n)$ per ogni $n$ intero e $p$ primo.

Edit: typo grz lello

[TeoricodeiNumeri]

Posto una soluzione parziale in attesa di risolverlo tutto (è un po' tecnica ma pace all'anima).

Testo nascosto:

Come prima cosa determiniamo un'espressione conveniente per la funzione $f(n)$. Noi sappiamo per definizione che \begin{equation} f(n)=\sum_{i\leq n ; (i,n)\neq 1} i \end{equation}

con $f(1)=0$ per convenzioni mie personali che non si discutono . Noi mostreremo che $f(n)=\binom{n+1}{2}-\sum_{d\vert n}\mu(d) d \binom{n/d+1}{2}$ dove $\mu(n)$ è la funzione di Moebius. In effetti ci sono un bel po' di modi di vedere questa cosa:

1) per il principio di inclusione-esclusione (ma non vi scrivo come perché tipograficamente sarebbe un casino);

2) per le proprietà delle convoluzioni di Dirichlet. Difatti, posto con $g(n)=\sum_{i \leq n; (i,n)=1} i$, risulta ovviamente che $f(n)+g(n)=\binom{n+1}{2}$ e $f(n)=[\sum_{d\vert n} d \cdot g(n/d)]-g(n)$, da cui per ogni $n$ naturale positivo vale che $\sum_{d\vert n} d\cdot g(n/d)=\binom{n+1}{2}$. Per l'associatività della convoluzione di Dirichlet e siccome l'inversa di $h(n)=n$ è $h^{-1}(n)=\mu(n) n$, abbiamo che $g(n)=\sum_{d\vert n} \mu(d) d \binom{n/d +1}{2}$.


Facendo un po' di conti sfruttando che $\sum_{d\vert n} \mu(d)\cdot \frac{n}{d}=\phi(n)$ e che per $n\geq 2$ vale $\sum_{d\vert n} \mu(d)=0$ si ottiene che per ogni $n\geq 2$ vale
\begin{equation}
f(n)=\frac{n(n+1-\phi(n))}{2}
\end{equation}

Ci chiediamo quindi quando vale
\begin{equation}

n(n+1-\phi(n))=(n+p)(n+p+1-\phi(n+p))
\end{equation}

per $p$ primo. Distinguiamo due casi:
1) $p$ non divide $n$, ovvero $(p,n)=1$. Allora $(n+p,n) =1$ e quindi per il Lemma di Euclide generalizzato vale che $n+p\vert n+1-\phi(n)$, ma $0<n+1-\phi(n)<n+p$, da cui non si sono soluzioni in questo caso.

2) $p\vert n$: boh, ancora non l'ho fatto.

[TeoricodeiNumeri]

Mi è stato fatto giustamente notare che per la parte in cui determino $f(n) $ c'è un metodo estremamente più veloce.

Testo nascosto:

se $(n, k) \neq 1$ allora anche $(n, n-k) \neq 1$ e viceversa. Scrivendo in riga i numeri da 0 a $n$ che non sono coprimi con $n$ in ordine crescente e riscrivendoli in ordine crescente da sotto abbiamo che la somma sulle righe della tabella costruita è $2f(n)$, mentre la somma sulle colonne è $n(n+1-\phi(n))$, da cui
\begin{equation}
f(n) =\frac{n(n+1-\phi(n))} {2} \end{equation}