Maths Olympiad Prep

Library / /34 of 36

Number theory Difficulty 6.6 National Olympiad Prove it 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)2n\tau(n)^2 \mid n with τ(n)\tau(n) is the number of positive divisors of nn.

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=p1a1p2a2pkakn = 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)2n\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 k3k \ge 3 then n(357)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 mZ+m \in \mathbb{Z}^+. Note that if 2m62m \ge 6 then τ(n)7\tau(n) \ge 7 so p7p \ge 7 and n76>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,bZ+a, b \in \mathbb{Z}^+. Note that if both 2a2a and 2b42b \ge 4 then n(35)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 92n9^2|n, is not satisfied; therefore 2a42a \ge 4 so n954>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 2a62a \ge 6 then n3652>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 uvu \neq v such that udvd(mod2027)u^d \equiv v^d \pmod{2027}. Let ss be the inverse of vv modulo 20272027 then let t=ust = us, we have td1(mod2027)t^d \equiv 1 \pmod{2027}. Next, let h=ord2027(t)h = \text{ord}_{2027}(t) then hdh \nmid d and by Fermat's little theorem h2026h \nmid 2026 so hgcd(d,2026)h \nmid \text{gcd}(d, 2026). Note that 2026=210132026 = 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
t1(mod2027)    us1(mod2027). t \equiv 1 \pmod{2027} \iff us \equiv 1 \pmod{2027}.
Multiplying both sides of this congruence by vv gives uv(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

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 reproduced verbatim; metadata (topic, difficulty) added by this project.