Bel probbo ggwp

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
Fenu
Messaggi: 77
Iscritto il: 10 set 2017, 16:34

Bel probbo ggwp

Messaggio da 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
Messaggi: 38
Iscritto il: 14 lug 2019, 09:58

Re: Bel probbo ggwp

Messaggio da 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.
Ultima modifica di TeoricodeiNumeri il 13 mag 2020, 19:33, modificato 1 volta in totale.
TeoricodeiNumeri
Messaggi: 38
Iscritto il: 14 lug 2019, 09:58

Re: Bel probbo ggwp

Messaggio da TeoricodeiNumeri »

Mi è stato fatto giustamente notare che per la parte in cui determino $f(n) $ c'è un metodo estremamente più veloce. :cry:
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}
Rispondi