For an integer $ n \geq 2 $, let $ s (n) $ be the sum of positive integers not exceeding $ n $ and not relatively prime to $ n $. a) Prove that $ s (n) = \dfrac {n} {2} \left (n + 1- \varphi (n) \right) $, where $ \varphi (n) $ is the number of integers positive cannot exceed $ n $ and are relatively prime to $ n $. b) Prove that there is no integer $ n \geq 2 $ such that $ s (n) = s (n + 2021) $
Problem
Source: VMO 2021 P4 Vietnam National Olympiad
Tags: number theory, Sum, phi function
27.12.2020 00:01
It should be not relatively prime to $n$ instead of not primes together with $n$.
27.12.2020 00:16
It is well known that the sum of the numbers less than n relatively prime to n is $\phi(n)$ because $\gcd(n,k)=\gcd(n-k,n)$ and $\phi(n)/2$ such pairs summing to $n/2$.
27.12.2020 08:26
Oh wait that was super easy...
27.12.2020 09:57
Somehow remind of this... But $2021=43 \times 47$, so extra work is needed.
27.12.2020 15:33
yofro wrote:
Oh wait that was super easy... This solution does not seem right. First, we may not have $s(n+2021)=s(n)+\ldots$, since $s$ does not mean the partial sums here. Another issue is when you use $\gcd(n+j,n+2021)=1\implies \gcd(j,2021)=1$. This is not true. Take $j=43$, $n=6$.
27.12.2020 15:34
Rickyminer wrote: Somehow remind of this... But $2021=43 \times 47$, so extra work is needed. Yes, indeed. The extra work is tremendous for now. Trying to reduce the amount of brute force checking. Here: https://math.stackexchange.com/questions/3962246/nn1-phin-n2021n2022-phin2021