Maths Olympiad Prep

Library / /433 of 462

Number theory Difficulty 7.3 National Olympiad, round 2 Prove it Ireland

Determine, with proof, the smallest positive integer NN for which the equation
x2y2=N x^2 - y^2 = N
has exactly 24 solutions (x,y)(x, y) with positive integers xx and yy.

Solution

Because N>0N > 0, we need to have x>y>0x > y > 0 for any solution. Since x2y2=(x+y)(xy)x^2 - y^2 = (x + y)(x - y), each solution gives a factorisation of NN into two factors, say N=abN = a \cdot b, where a=x+y>xy=ba = x + y > x - y = b.
If we start with a factorisation N=abN = a \cdot b with a>ba > b, there is at most one solution (x,y)(x, y) corresponding to this factorisation of NN, namely
x=a+b2y=ab2. x = \frac{a+b}{2} \qquad y = \frac{a-b}{2}.
The condition on a,ba, b for giving an integer solution (x,y)(x, y) is ab(mod2)a \equiv b \pmod 2 so that a+ba + b and aba - b are both even. If NN is odd, any factorisation into two positive integers will give a solution. When NN is even, however, both factors must be even and N=4MN = 4M for some integer MM. Each factorisation of MM into two non-equal factors will then provide a solution.

To find all factorisations of NN, we write N=p1a1p2a2p3a3pkakN = p_1^{a_1} p_2^{a_2} p_3^{a_3} \cdots p_k^{a_k} where all ai>0a_i > 0 and p1<p2<<pkp_1 < p_2 < \cdots < p_k. It is well known that the number of positive divisors of nn is then equal to τ(N)=(a1+1)(a2+1)(ak+1)\tau(N) = (a_1 + 1)(a_2 + 1)\cdots(a_k + 1). If τ(N)\tau(N) is even, which is the case precisely when NN is not a perfect square, the number of factorisations of NN into two factors is equal to τ(N)/2\tau(N)/2. If NN is a square, we only get (τ(N)1)/2(\tau(N) - 1)/2 factorisations with a>ba > b.
For the equation to have exactly 24 solutions, we need to use NN odd with τ(N)=48\tau(N) = 48 or τ(N)=49\tau(N) = 49, or N=4MN = 4M with τ(M)=48\tau(M) = 48 or τ(M)=49\tau(M) = 49. There is no need to consider N=4MN = 4M with odd MM since M<4MM < 4M and we are looking for the smallest NN.
Because ai>0a_i > 0 for all ii, there are only two possibilities to obtain τ(N)=(a1+1)(a2+1)(ak+1)=72=49\tau(N) = (a_1 + 1)(a_2 + 1)\cdots(a_k + 1) = 7^2 = 49, namely k=1k = 1 and a1=48a_1 = 48, or k=2k = 2 and a1=a2=6a_1 = a_2 = 6.

The smallest odd N=p148N = p_1^{48} is 3483^{48}. The smallest N=4MN = 4M is 2502^{50} where we have used M=248M = 2^{48}. Clearly, 348=2716>1616=264>2503^{48} = 27^{16} > 16^{16} = 2^{64} > 2^{50}.
The smallest odd N=p16p26N = p_1^6 p_2^6 is N=3656N = 3^6 \cdot 5^6. The smallest N=4MN = 4M is N=2836N = 2^8 \cdot 3^6 with M=2636M = 2^6 \cdot 3^6. Note that 250=28421>28362^{50} = 2^8 \cdot 4^{21} > 2^8 \cdot 3^6 and 3656>3644=28363^6 \cdot 5^6 > 3^6 \cdot 4^4 = 2^8 \cdot 3^6. Hence, the smallest NN we found so far is N0=2836N_0 = 2^8 \cdot 3^6.

We now aim at finding all NN for which τ(N)=48=324\tau(N) = 48 = 3 \cdot 2^4. Since ai+12a_i + 1 \ge 2 we can have at most k=5k=5 different prime factors in NN. We distinguish cases according to the number kk. We will always assure that a1a2aka_1 \ge a_2 \ge \dots \ge a_k, because this gives the smallest possible odd NN when p1<p2<<pkp_1 < p_2 < \dots < p_k are the kk smallest odd primes. When we allow p1=2p_1 = 2, we need to consider N=4MN = 4M, i.e. N=p1a1+2p2a2p3a3pkakN = p_1^{a_1+2} p_2^{a_2} p_3^{a_3} \cdots p_k^{a_k} with p1=2p_1 = 2.
**Case 1 (k=5k=5):** The only option here is a1=2a_1 = 2 and a2=a3=a4=a5=1a_2 = a_3 = a_4 = a_5 = 1, which leads to N=p12p2p3p4p5N = p_1^2 p_2 p_3 p_4 p_5 and the smallest odd number of this shape is N1=32571113N_1 = 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13. The smallest even number N=4MN = 4M we obtain here is N2=42235711=2435711N_2 = 4 \cdot 2^2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 = 2^4 \cdot 3 \cdot 5 \cdot 7 \cdot 11.

(5,1,1,1)(3,2,1,1) (5, 1, 1, 1) \quad (3, 2, 1, 1)
The smallest odd NN here are N3=355711N_3 = 3^5 \cdot 5 \cdot 7 \cdot 11 and N5=3352711N_5 = 3^3 \cdot 5^2 \cdot 7 \cdot 11. The smallest even numbers are N4=27357N_4 = 2^7 \cdot 3 \cdot 5 \cdot 7 and N6=253257N_6 = 2^5 \cdot 3^2 \cdot 5 \cdot 7, respectively.

**Case 3 (k=3k=3):** There are four possibilities for (a1,a2,a3)(a_1, a_2, a_3):
(11,1,1)(5,3,1)(7,2,1)(3,3,2) (11, 1, 1) \quad (5, 3, 1) \quad (7, 2, 1) \quad (3, 3, 2)
This leads to the following eight possibilities for NN:
(11,1,1)N7=31157N8=21335(5,3,1)N9=35537N10=27335(7,2,1)N11=37527N12=29325(3,3,2)N13=335372N14=253352 \begin{array}{lll} (11, 1, 1) & N_7 = 3^{11} \cdot 5 \cdot 7 & N_8 = 2^{13} \cdot 3 \cdot 5 \\ (5, 3, 1) & N_9 = 3^5 \cdot 5^3 \cdot 7 & N_{10} = 2^7 \cdot 3^3 \cdot 5 \\ (7, 2, 1) & N_{11} = 3^7 \cdot 5^2 \cdot 7 & N_{12} = 2^9 \cdot 3^2 \cdot 5 \\ (3, 3, 2) & N_{13} = 3^3 \cdot 5^3 \cdot 7^2 & N_{14} = 2^5 \cdot 3^3 \cdot 5^2 \end{array}

**Case 4 (k=2k=2):** There are four possibilities for (a1,a2)(a_1, a_2):
(23,1)(11,3)(7,5)(15,2) (23, 1) \quad (11, 3) \quad (7, 5) \quad (15, 2)
This leads to the following eight possibilities for NN:
(23,1)N15=3235N16=2253(11,3)N17=31153N18=21333(7,5)N19=3755N20=2935(15,2)N21=31552N22=21732 \begin{array}{lll} (23, 1) & N_{15} = 3^{23} \cdot 5 & N_{16} = 2^{25} \cdot 3 \\ (11, 3) & N_{17} = 3^{11} \cdot 5^3 & N_{18} = 2^{13} \cdot 3^3 \\ (7, 5) & N_{19} = 3^7 \cdot 5^5 & N_{20} = 2^9 \cdot 3^5 \\ (15, 2) & N_{21} = 3^{15} \cdot 5^2 & N_{22} = 2^{17} \cdot 3^2 \end{array}

Case 5 (k = 1): The only option is a1=23a_1 = 23 leading to odd N23=323N_{23} = 3^{23} and even N24=225N_{24} = 2^{25}.

To find the smallest value of NN, we first note that 2a+2<3a2^{a+2} < 3^a for all a4a \ge 4. This is easily shown by induction. This implies that N2m<N2m1N_{2m} < N_{2m-1} for all m=1,2,,12m = 1, 2, \dots, 12 except for m=1,3,7m = 1, 3, 7. After cancelling common factors, it is easy to see that
N2=2435711<N1=32571113N6=253257<N5=3352711N14=253352<N13=335372. \begin{align*} N_2 &= 2^4 \cdot 3 \cdot 5 \cdot 7 \cdot 11 < N_1 = 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \\ N_6 &= 2^5 \cdot 3^2 \cdot 5 \cdot 7 < N_5 = 3^3 \cdot 5^2 \cdot 7 \cdot 11 \\ N_{14} &= 2^5 \cdot 3^3 \cdot 5^2 < N_{13} = 3^3 \cdot 5^3 \cdot 7^2. \end{align*}
This shows that the smallest NN is one of the N2mN_{2m} where m=0,1,2,,12m = 0, 1, 2, \dots, 12. If we compare all N2mN_{2m} with N6N_6 we will find that N6=253257=10080N_6 = 2^5 \cdot 3^2 \cdot 5 \cdot 7 = 10080 is the smallest positive NN for which x2y2=Nx^2 - y^2 = N has exactly 24 solutions in positive integers.

To show N6<N2mN_6 < N_{2m} in each case we cancel the common factors of these two numbers. To reduce our work, we may first observe that 3257=316<293^2 \cdot 5 \cdot 7 = 316 < 2^9, hence when N2mN_{2m} has a factor 2a2^a with a14a \ge 14 it is clear that N6<N2mN_6 < N_{2m}. Similarly, N6<N2mN_6 < N_{2m} when N2mN_{2m} has a factor 2a32^a \cdot 3 with a12a \ge 12, because 357=105<273 \cdot 5 \cdot 7 = 105 < 2^7. Finally, since 57=35<265 \cdot 7 = 35 < 2^6, whenever N2mN_{2m} has a factor 2a322^a \cdot 3^2 with a11a \ge 11 we also have N6<N2mN_6 < N_{2m}. This last case can be extended to those N2mN_{2m} that have a factor 2a32+i2^a \cdot 3^{2+i} with a11ia \ge 11-i.

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.