Maths Olympiad Prep

Track / Stage 6 / 310 of 400 #1950 of 2604

Problem 1950

National Olympiad, first round
Number theory Difficulty 6.6 Prove it Saudi Booklet · Saudi Arabia

Find all positive integers n<2027n < 2027 that satisfy the following conditions:
(i) For every positive divisor dd of nn, numbers 1d,2d,…,2026d1^d, 2^d, \dots, 2026^d all have distinct remainders when divided by 20272027.
(ii) τ(n)2∣n\tau(n)^2 \mid n with τ(n)\tau(n) is the number of positive divisors of nn.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Let call the numbers satisfying the given condition as "good" number. Consider some good number nn. One can see that if nn is even, then d=2d = 2 is a divisor of 22, however, then 121^2 and 202622026^2 both divide 20272027 with remainder 11, which does not satisfy. Therefore, nn is odd. We see that n=1n = 1 satisfies the given condition.

Now consider n>1n > 1 and set n=p1a1p2a2…pkakn = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k} with p1,p2,…,pkp_1, p_2, \dots, p_k being distinct odd primes and a1,a2,…,aka_1, a_2, \dots, a_k positive integers. Since τ(n)2∣n\tau(n)^2 \mid n, τ(n)\tau(n) is also odd.

We have τ(n)=(a1+1)(a2+1)⋯(ak+1)\tau(n) = (a_1+1)(a_2+1)\cdots(a_k+1) which is odd, so a1,a2,…,aka_1, a_2, \dots, a_k are all even. Therefore, nn must be a perfect square. Note that if k≥3k \ge 3 then n≥(3⋅5⋅7)2>2027n \ge (3 \cdot 5 \cdot 7)^2 > 2027, is not satisfied. Hence k∈{1;2}k \in \{1; 2\}. We consider the following cases.

1. If k=1k = 1 then n=p2mn = p^{2m} with pp being an odd prime and m∈Z+m \in \mathbb{Z}^+. Note that if 2m≥62m \ge 6 then τ(n)≥7\tau(n) \ge 7 so p≥7p \ge 7 and n≥76>2027n \ge 7^6 > 2027, does not satisfy. Therefore, we reduce to considering if 2m=22m = 2 then p=3p = 3 so n=9n = 9; and if 2m=42m = 4 then τ(n)=5\tau(n) = 5 so p=5p = 5, which implies n=54=625n = 5^4 = 625. We can check that the numbers n=9,n=625n = 9, n = 625 all satisfy condition (ii).

2. If k=2k = 2 then n=p2aq2bn = p^{2a}q^{2b} with p,qp, q being distinct odd primes and a,b∈Z+a, b \in \mathbb{Z}^+. Note that if both 2a2a and 2b≥42b \ge 4 then n≥(3⋅5)4>2027n \ge (3 \cdot 5)^4 > 2027, is not satisfied. Therefore, we can assume 2b=22b = 2, which implies that 3∣τ(n)3|\tau(n) so p=3p = 3 or q=3q = 3.

a. If q=3q = 3 then n=9p2an = 9p^{2a}, then if 2a=22a = 2 then τ(n)=9\tau(n) = 9 so 92∣n9^2|n, is not satisfied; therefore 2a≥42a \ge 4 so n≥9⋅54>2027n \ge 9 \cdot 5^4 > 2027, is also not satisfied.

b. If p=3p = 3 then n=32aq2n = 3^{2a}q^2; if 2a=22a = 2 then the same absurdity exists, so 2a>22a > 2. But if 2a≥62a \ge 6 then n≥36⋅52>2027n \ge 3^6 \cdot 5^2 > 2027, is not satisfied. Therefore 2a=42a = 4 and 5∣τ(n)5|\tau(n) so q=5q = 5, implies n=2025n = 2025. We see that this number satisfies condition (ii).

Therefore n∈{9;625;2025}n \in \{9; 625; 2025\}. We will prove that these numbers are good.

Consider an arbitrary positive divisor dd of nn then dd is odd. Suppose there exist u,v∈{1;2;… ;2026}u, v \in \{1; 2; \dots; 2026\} and u≠vu \neq v such that ud≡vd(mod2027)u^d \equiv v^d \pmod{2027}. Let ss be the inverse of vv modulo 20272027 then let t=ust = us, we have td≡1(mod2027)t^d \equiv 1 \pmod{2027}. Next, let h=ord2027(t)h = \text{ord}_{2027}(t) then h∤dh \nmid d and by Fermat's little theorem h∤2026h \nmid 2026 so h∤gcd(d,2026)h \nmid \text{gcd}(d, 2026). Note that 2026=2⋅10132026 = 2 \cdot 1013 with 10131013 being a prime number, it is easy to see that gcd(d,2026)=1\text{gcd}(d, 2026) = 1 and h=1h = 1. Then, we will have
t≡1(mod2027)  ⟺  us≡1(mod2027). t \equiv 1 \pmod{2027} \iff us \equiv 1 \pmod{2027}.
Multiplying both sides of this congruence by vv gives u≡v(mod2027)u \equiv v \pmod{2027}, which is absurd. Thus, all positive divisors dd of these nn satisfy condition (i).

So all the good numbers are 1,9,625,20251, 9, 625, 2025. □\square

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.