Maths Olympiad Prep

Library / /26 of 53

Number theory Difficulty 6.6 National olympiad Prove it Vietnam

For every pair of positive integers n,mn, m with n<mn < m, denote s(n,m)s(n, m) as the number of positive integers in the range [n,m][n, m] that are coprime with mm. Find all positive integers m2m \ge 2 such that mm satisfies these conditions

i) s(n,m)mns(1,m)m\frac{s(n, m)}{m-n} \ge \frac{s(1, m)}{m} for all n=1,2,,m1n = 1, 2, \dots, m-1.
ii) 2022m+12022^m + 1 is divisible by m2m^2.

Solution

Firstly, we prove that if mm satisfies the first condition, then mm has only one prime divisor. Assume that mm has at least 2 prime divisors, let pp be the smallest prime divisor of mm and p1,p2,,pkp_1, p_2, \dots, p_k be the remaining prime divisors of mm. We have
φ(m)m=(11p)(11p1)(11pk)<11p=p1p. \frac{\varphi(m)}{m} = \left(1 - \frac{1}{p}\right) \left(1 - \frac{1}{p_1}\right) \dots \left(1 - \frac{1}{p_k}\right) < 1 - \frac{1}{p} = \frac{p-1}{p}.
Hence, by choosing n=pn = p in i), one can get
s(p,m)mp=φ(m)(p1)mp<φ(m)φ(m)mpmp=φ(m)m=s(1,m)m, \frac{s(p, m)}{m-p} = \frac{\varphi(m) - (p-1)}{m-p} < \frac{\varphi(m) - \frac{\varphi(m)}{m} \cdot p}{m-p} = \frac{\varphi(m)}{m} = \frac{s(1, m)}{m},
which is a contradiction. Therefore, mm must be a power of a prime. Let m=pkm = p^k, note that
2022pk+12022+120230(modp), 2022^{p^k} + 1 \equiv 2022 + 1 \equiv 2023 \equiv 0 \pmod{p},
thus p2023p \mid 2023 and p{7,17}p \in \{7, 17\}.
If p=7p = 7, using LTE, we have
v7(20227k+1)=v7(2023)+v7(7k)=1+kv7(72k)=2k. v_7(2022^{7k} + 1) = v_7(2023) + v_7(7^k) = 1 + k \ge v_7(7^{2k}) = 2k.
From this, we conclude that k=1k = 1 and m=7m = 7. Similarly, for p=17p = 17, applying LTE, we also have
v17(202217k+1)=v17(2023)+v17(17k)=2+kv17(172k)=2k, v_{17}(2022^{17k} + 1) = v_{17}(2023) + v_{17}(17^k) = 2 + k \ge v_{17}(17^{2k}) = 2k,
so k{1,2}k \in \{1, 2\} and m{17,289}m \in \{17, 289\}.
Therefore, m=7,17,289m = 7, 17, 289 are all desired numbers. \square

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.