Maths Olympiad Prep

Library / /23 of 63

Number theory Difficulty 6.5 National olympiad Prove it Japan

Determine the number of pairs (p,a)(p, a) of a prime number pp and an integer aa such that p3p \ge 3, 1a20241 \le a \le 2024, and the following condition is satisfied:
a<p4a < p^4 holds and ap4+2p3+2p2+1ap^4 + 2p^3 + 2p^2 + 1 is a square number.

Solution

When the condition is satisfied, there exists a non-negative integer nn such that ap4+2p3+2p2+1=n2ap^4 + 2p^3 + 2p^2 + 1 = n^2 and then
(ap22p1)p4=n2(p3+p2+1)2=(n+p3+p2+1)(np3p21)() (a - p^2 - 2p - 1)p^4 = n^2 - (p^3 + p^2 + 1)^2 = (n + p^3 + p^2 + 1)(n - p^3 - p^2 - 1) \quad (*)
holds. If we assume that both n+p3+p2+1n + p^3 + p^2 + 1 and np3p21n - p^3 - p^2 - 1 are divisible by pp, then n+10n1(modp)n + 1 \equiv 0 \equiv n - 1 \pmod p, leading to 20(modp)2 \equiv 0 \pmod p, which contradicts the assumption that pp is an odd prime. Therefore, at least one of n+p3+p2+1,np3p21n + p^3 + p^2 + 1, n - p^3 - p^2 - 1 is not divisible by pp. Since the left hand side of (*) is divisible by p4p^4, one of n+p3+p2+1,np3p21n + p^3 + p^2 + 1, n - p^3 - p^2 - 1 is divisible by p4p^4.
In the case n+p3+p2+1n + p^3 + p^2 + 1 is divisible by p4p^4, there exists a positive integer kk such that n=kp4p3p21n = kp^4 - p^3 - p^2 - 1. By substituting this into (*), we obtain (ap22p1)p4=kp4(kp42p32p22)(a - p^2 - 2p - 1)p^4 = kp^4(kp^4 - 2p^3 - 2p^2 - 2), hence a=p2+2p+1+k(kp42p32p22)a = p^2 + 2p + 1 + k(kp^4 - 2p^3 - 2p^2 - 2). If k2k \ge 2, we have
a>4(p4p3p21)=4p4(11p1p21p4)4p4(11319181)>p4 a > 4(p^4 - p^3 - p^2 - 1) = 4p^4 \left(1 - \frac{1}{p} - \frac{1}{p^2} - \frac{1}{p^4}\right) \ge 4p^4 \left(1 - \frac{1}{3} - \frac{1}{9} - \frac{1}{81}\right) > p^4
which contradicts a<p4a < p^4. If k=1k = 1, then a=p42p3p2+2p1=(p2p1)22a = p^4 - 2p^3 - p^2 + 2p - 1 = (p^2 - p - 1)^2 - 2. In this case, by p3p \ge 3 we get 2p2p1<p22 \le p^2 - p - 1 < p^2 and then 1a<p41 \le a < p^4. Therefore, the number of pairs (p,a)(p, a) satisfying the condition is equal to the number of odd prime pp such that (p2p1)222024(p^2 - p - 1)^2 - 2 \le 2024, and there exist three such primes p=3,5,7p = 3, 5, 7.
In the case np3p21n - p^3 - p^2 - 1 is divisible by p4p^4, there exists a non-negative integer kk such that n=kp4+p3+p2+1n = kp^4 + p^3 + p^2 + 1. By substituting this to (*), we obtain (ap22p1)p4=kp4(kp4+2p3+2p2+2)(a - p^2 - 2p - 1)p^4 = kp^4(kp^4 + 2p^3 + 2p^2 + 2), hence a=p2+2p+1+k(kp4+2p3+2p2+2)a = p^2 + 2p + 1 + k(kp^4 + 2p^3 + 2p^2 + 2). If k1k \ge 1, then we have a>p4a > p^4 which contradicts a<p4a < p^4. If k=0k = 0, then we have a=p2+2p+1=(p+1)2a = p^2 + 2p + 1 = (p+1)^2. In this case, by p3p \ge 3 we get 1<(p+1)2<(p2)2=p41 < (p+1)^2 < (p^2)^2 = p^4 and then 1a<p41 \le a < p^4. Therefore, the number of pairs (p,a)(p, a) satisfying the condition is equal to the number of odd prime pp such that (p+1)22024(p+1)^2 \le 2024, and there exist 13 such primes p=3,5,7,11,13,17,19,23,29,31,37,41,43p = 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43.
We have proved that the total number of pairs (p,a)(p, a) satisfying the condition is 3+13=163 + 13 = 16.

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.