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
XbenX
27.12.2020 00:01
It should be not relatively prime to $n$ instead of not primes together with $n$.
Williamgolly
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$.
yofro
27.12.2020 08:26
Claim: It suffices to show that there doesn't exist a positive integer $k$ such that $n<k<n+2021$ and $\gcd(k,n+2021)\ne 1$.
Proof: Suppose there does exist such a $k$, in fact let there exist satisfactory $k_1,k_2,...,k_i$. This would imply $s(n+2021)=s(n)+\sum_{r=1}^{i}k_r$, a clear contradiction since $k_j>n$.
Write $k=n+j$. We want $\gcd(n+j, n+2021)=1\implies \gcd(j, 2021)=1$. There exists many such $j$, an example is $1$. We're done. $\blacksquare$
Oh wait that was super easy...
Rickyminer
27.12.2020 09:57
Somehow remind of this... But $2021=43 \times 47$, so extra work is needed.
i707107
27.12.2020 15:33
yofro wrote:
Claim: It suffices to show that there doesn't exist a positive integer $k$ such that $n<k<n+2021$ and $\gcd(k,n+2021)\ne 1$.
Proof: Suppose there does exist such a $k$, in fact let there exist satisfactory $k_1,k_2,...,k_i$. This would imply $s(n+2021)=s(n)+\sum_{r=1}^{i}k_r$, a clear contradiction since $k_j>n$.
Write $k=n+j$. We want $\gcd(n+j, n+2021)=1\implies \gcd(j, 2021)=1$. There exists many such $j$, an example is $1$. We're done. $\blacksquare$
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$.
i707107
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