Maths Olympiad Prep

Library / /5 of 7

, 2021

Number theory Difficulty 7.1 National olympiad, round 2 Prove it Vietnam

For each integer n2n \ge 2, let s(n)s(n) denote the sum of all positive integers that are at most nn and not relatively prime to nn.
a) Prove that s(n)=n2(n+1φ(n))s(n) = \frac{n}{2}(n+1-\varphi(n)), where φ(n)\varphi(n) is the number of positive integers that are at most nn and are relatively prime to nn.
b) Prove that there does not exist an integer n2n \ge 2 such that
s(n)=s(n+2021). s(n) = s(n + 2021).

Solution

a) Notice that if kk is a positive integer such that gcd(k,n)=1\gcd(k, n) = 1 and k<nk < n then nkn-k and nn are relatively prime. It follows that
kn,gcd(k,n)=1k=kn,gcd(k,n)=1(nk) \sum_{k \le n, \gcd(k,n)=1} k = \sum_{k \le n, \gcd(k,n)=1} (n-k)
Let A={kN1kn,gcd(k,n)=1={k1,k2,,kn}}A = \{k \in \mathbb{N} \mid 1 \le k \le n, \gcd(k, n) = 1 = \{k_1, k_2, \dots, k_n\}\} then
i=1φ(n)ki=12i=1φ(n)ki+12i=1φ(n)(nki)=12i=1φ(n)(ki+nki)=nφ(n)2 \sum_{i=1}^{\varphi(n)} k_i = \frac{1}{2} \sum_{i=1}^{\varphi(n)} k_i + \frac{1}{2} \sum_{i=1}^{\varphi(n)} (n - k_i) = \frac{1}{2} \sum_{i=1}^{\varphi(n)} (k_i + n - k_i) = \frac{n\varphi(n)}{2}
So, we have
s(n)=i=1nii=1φ(n)ki=n(n+1)2nφ(n)2=n2(n+1φ(n)). s(n) = \sum_{i=1}^{n} i - \sum_{i=1}^{\varphi(n)} k_i = \frac{n(n+1)}{2} - \frac{n\varphi(n)}{2} = \frac{n}{2}(n+1-\varphi(n)).

b) Suppose that there exists a positive integer nn such that s(n)=s(n+2021)s(n) = s(n + 2021). Thus,
2s(n)=n(n+1φ(n))=(n+2021)(n+2022φ(n+2021))() 2s(n) = n(n + 1 - \varphi(n)) = (n + 2021)(n + 2022 - \varphi(n + 2021)) \quad (*)
or
2021(2n+2022φ(n+2021))=n(φ(n+2021)φ(n))(1) 2021(2n + 2022 - \varphi(n + 2021)) = n(\varphi(n + 2021) - \varphi(n)) \quad (1)
From (*), it follows that n,n+2021n, n + 2021 are divisors of 2s(n)2s(n). Otherwise,
2s(n)=n(n+1)nφ(n)<n(n+1)<n(n+2021), 2s(n) = n(n + 1) - n\varphi(n) < n(n + 1) < n(n + 2021),
so n,n+2021n, n + 2021 are not coprime, which means (n,2021)1(n, 2021) \neq 1. Let d=gcd(n,2021)>1d = \gcd(n, 2021) > 1, so gcd(nd,2021d)=1\gcd(\frac{n}{d}, \frac{2021}{d}) = 1. From (1), we get
2021d(2n+2022φ(n+2021))=nd(φ(n+2021)φ(n))(2) \frac{2021}{d}(2n + 2022 - \varphi(n + 2021)) = \frac{n}{d}(\varphi(n + 2021) - \varphi(n)) \quad (2)
so there exists some positive integer xx such that
φ(n+2021)φ(n)=2021dx(3) \varphi(n + 2021) - \varphi(n) = \frac{2021}{d} \cdot x \quad (3)
2n+2022φ(n+2021)=ndx(4) 2n + 2022 - \varphi(n + 2021) = \frac{n}{d} \cdot x \quad (4)
Thus, φ(n+2021)φ(n)\varphi(n + 2021) - \varphi(n) is divisible by 2021/d2021/d. Otherwise, one can check that φ(n+2021),φ(n)\varphi(n + 2021), \varphi(n) is divisible by φ(d)\varphi(d) and gcd(φ(d),2021/d)=1\gcd(\varphi(d), 2021/d) = 1 for all d{43,47,2021}d \in \{43, 47, 2021\}, so
φ(n+2021)φ(n):2021φ(d)d \varphi(n + 2021) - \varphi(n) : \frac{2021\varphi(d)}{d}
On the other hand, it follows from (3) and (4)
d<x=d2n+2022φ(n)n+2021<2d d < x = d \cdot \frac{2n + 2022 - \varphi(n)}{n + 2021} < 2d
It implies that, for all d{43,47,2021}d \in \{43, 47, 2021\}
2021φ(d)d<2021dd<2021dx<22021<32021φ(d)d \frac{2021\varphi(d)}{d} < \frac{2021 \cdot d}{d} < \frac{2021}{d} \cdot x < 2 \cdot 2021 < \frac{3 \cdot 2021\varphi(d)}{d}
Thus, φ(n+2021)φ(n)=22021φ(d)/d\varphi(n + 2021) - \varphi(n) = 2 \cdot 2021\varphi(d)/d and x=2φ(d)x = 2\varphi(d), so
φ(n+2021)=2n(dφ(d))d+2022(5) \varphi(n + 2021) = \frac{2n(d - \varphi(d))}{d} + 2022 \quad (5)
φ(n)=2n(dφ(d))d+202222021φ(d)d(6) \varphi(n) = \frac{2n(d - \varphi(d))}{d} + 2022 - \frac{2 \cdot 2021\varphi(d)}{d} \quad (6)
If nn has at most 10 distinct prime divisors then
φ(n)>ni=211(11i)=n11>2n(dφ(d))d,d{43,47,2021}, \varphi(n) > n \prod_{i=2}^{11} \left(1 - \frac{1}{i}\right) = \frac{n}{11} > \frac{2n(d - \varphi(d))}{d}, d \in \{43, 47, 2021\},
which contradicts (6). We get nn has at least 11 distinct prime divisors, so n>12!n > 12! and φ(n)\varphi(n) is divisible by 2102^{10}.
Similarly, if n+2021n + 2021 has at most 4 distinct prime divisors then
φ(n+2021)>(n+2021)i=25(11i)=n+20215. \varphi(n + 2021) > (n + 2021) \prod_{i=2}^{5} \left(1 - \frac{1}{i}\right) = \frac{n + 2021}{5}.
Otherwise, n>12!n > 12! and
n+20215>2n(dφ(d))d+2022,d{43,47,2021}, \frac{n + 2021}{5} > \frac{2n(d - \varphi(d))}{d} + 2022, d \in \{43, 47, 2021\},
which contradicts (5). We get n+2021n + 2021 has at least 5 distinct prime divisors, so φ(n+2021)\varphi(n + 2021) is divisible by 242^4.
On the other hand
v2(φ(n+2021)φ(n))=v2(22021φ(d)d)3,d{43,47,2021} v_2(\varphi(n + 2021) - \varphi(n)) = v_2\left(\frac{2 \cdot 2021\varphi(d)}{d}\right) \le 3, \forall d \in \{43, 47, 2021\}
which contradicts φ(n+2021):24\varphi(n + 2021):2^4 and φ(n):211\varphi(n):2^{11}. Hence, there does not exist a positive integer nn such that s(n)=s(n+2021)s(n) = s(n + 2021)

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.