[tex]f(n) \neq f(m)[/tex] se [tex]m-n \in \mathbb{P}[/tex]

[jordan]

Per ogni intero $ n\ge 2 $, definiamo $ f(n):=\displaystyle \sum_{1\le i\le n, \text{gcd}(i,n)=1}{i} $.

Mostrare che se $ f(n) = f(m) $ per qualche intero $ m\ge n+2 $ allora $ m-n $ non è primo.

(Balkan MO 2010)

[Leonida]

Claim: $f(n) = \displaystyle \frac{n \cdot \varphi(n)}{2}$.
Sia $S$ la sommatoria nel testo. Gli addendi che compaiono in $S$ sono proprio $\varphi(n)$. Inoltre per le proprietà del M.C.D, $(i,n) = (n-i, n)$; pertanto se $i$ compare nella sommatoria, allora compare anche $n-i$. Si può quindi vedere $S$ come una somma di $\displaystyle \frac{\varphi(n)}{2}$ coppie, ognuna delle quali ha somma $n$, da cui il Claim.
Dimostro ora una cosa equivalente alla tesi (che poi è anche il titolo del topic): se $m -n \in \mathbb{P}$ allora $f(m) \neq f(n)$.
Sia $m= n +p$, con $p \in \mathbb{P}$. La tesi diventa $f(n +p) \neq f(n) \rightarrow (n +p)\varphi(n +p) \neq n \varphi(n)$.
Suppongo per assurdo valga l'uguaglianza: $(n +p)\varphi(n +p) = n \varphi(n)$.
Se $q = \text{gpf}(n+p) > \text{gpf}(n)$ allora $q \nmid n$ e $q \nmid \varphi (n)$, dato che $\text{gpf}(\varphi(n)) \leq \text{gpf}(n) < q$, pertanto trovo un assurdo modulo $q$.
Se $\text{gpf}(n+p) < \text{gpf}(n) = r$ analogamente al caso precedente $r \nmid (n +p) \varphi(n +p)$, assurdo modulo $r$.
Altrimenti $\text{gpf}(n+p) = \text{gpf}(n) = d$: quindi $d \mid n+p -n = p \rightarrow d = p$.
Sia $v_p(n) = \alpha, \alpha > 1$: segue che $v_p(n +p) = \min (\alpha,1) = 1$; dato che $p = \text{gpf}(n) = \text{gpf}(n +p)$, allora $v_p(\varphi(n)) = \alpha -1$ e $v_p(\varphi(n+p)) = 0$ e quindi trovo un assurdo modulo $p^{\alpha -1}$ nell'uguaglianza. Ne deduco che $v_p(n) = v_p(n +p) = 1$.
Ora posso porre $n=kp, n+p = (k+1)p$, con $(k,p)=(k+1,p) =1$. Sostituisco nell'uguaglianza: $(k+1)p \cdot \varphi((k+1)p) = kp \cdot \varphi(kp) \rightarrow (k+1) \varphi(p) \cdot \varphi(k+1) = k \varphi(p) \cdot \varphi(k) \rightarrow (k+1) \cdot \varphi(k+1) = k \cdot \varphi(k)$.
Ma ora abbiamo finito: infatti deve valere $k \cdot \varphi(k) \equiv 0 \pmod{k+1} \rightarrow \varphi(k) \equiv 0 \pmod{k+1}$, ma ciò è assurdo perchè $\varphi(k) < k < k+1$.

P.S.: ma nel testo delle Balkan non era la somma dei numeri non coprimi con n?

[jordan]

P.S.: ma nel testo delle Balkan non era la somma dei numeri non coprimi con n?

Si, lho notato solo ora.. Comunque, Bene

Copio anche la dimostrazione di fry (Santana qui sull'oliforum), ma e' sostanzialmente la stessa:

È noto, ed eventualmente lo posso dimostrare, che $ f(1) = 1 $ e $ f(n) = \frac1{2}\,n\, \varphi(n) $ per ogni intero $ n \geq 2 $, dove $ \varphi $ è l'indicatore di Eulero. Ora se $ f(m) = f(n) $ per due interi $ m \geq n + 2 \geq 3 $ allora: $ n=1 $ e $ \frac1{2}\,m\,\varphi(m) = 1 $, cioè $ m = 2 / \varphi(m) \leq 2 $, assurdo; oppure $ n \geq 2 $ e $ m\,\varphi(m) = n\,\varphi(n) $. Se $ \gcd(m,n) = 1 $ allora $ m \mid \varphi(n) \leq n $ mentre $ n \mid \varphi(m) \leq m $, cioè $ m=n $, assurdo. Se invece $ \gcd(m,n) \geq 2 $ allora supponiamo che $ p=m-n $ sia primo. Abbiamo $ \gcd(m,n) \mid p $ e quindi $ \gcd(m,n) = p $, da cui $ m=p(k+1) $ e $ n=pk $ per un opportuno intero $ k \geq 1 $. Pertanto $ (k+1) \varphi(p(k+1)) = k \varphi(pk) $. Se $ p \nmid k, k+1 $ allora $ (k+1) \varphi(k+1) = k \varphi(k) $ ovvero $ k+1 \mid \varphi(k) \leq k $, assurdo. Se $ p \mid k $ allora $ (k+1) (p-1) \varphi(k+1) = k \varphi(pk) = k p^{v_p(k)} (p-1) \varphi(k / p^{v_p(k)}) $ cioè $ k +1 \mid \varphi(k / p^{v_p(k)}) \leq k / p < k $, assurdo. Infine se $ p \mid k+1 $ allora $ k (p-1)\varphi(k) = (k+1)p^{v_p(k+1)}(p-1) \varphi((k+1) / p^{v_p(k+1)}) $ da cui $ k \mid \varphi((k+1) / p^{v_p(k+1)}) \leq (k+1) / p \leq (k+1) / 2 $ ovvero $ k=1 $, $ p=2 $, $ m=4 $ e $ n=2 $, però vale $ m\,\varphi(m) \neq n\,\varphi(n) $, assurdo. []