Maths Olympiad Prep

Library / /6 of 8

Number theory Difficulty 5.6 AIME, harder Prove it Italy

Problem:
Find all ordered triples of positive integers (p,q,n)(p, q, n) such that p,qp, q are primes and p2+q2=pqn+1p^{2}+q^{2}=p q n+1.

Solution

Solution:
Suppose p=qp=q. Substituting we obtain p2(2n)=1p^{2}(2-n)=1 which is impossible because 1 is not divided by any prime. Hence necessarily pp and qq are different; since the equation is symmetric in pp and qq we may assume that q>pq>p, that is qp+1q \geq p+1. Let us now write our equation as:
p21=pqnq2=q(pnq). p^{2}-1=p q n-q^{2}=q(p n-q) .
This means that p21p^{2}-1 is a multiple of qq and therefore qq is a prime divisor of p21p^{2}-1. Hence
qp21=(p1)(p+1). q \mid p^{2}-1=(p-1)(p+1) .
Now, since qq is a prime number, it must appear either in the factorization of p1p-1 or in that of p+1p+1; in either case qp+1q \leq p+1. By the initial hypothesis we had qp+1q \geq p+1 and therefore we get q=p+1q=p+1. Between two consecutive numbers one must necessarily be even and hence equal to 2 (the only even prime) and the other is necessarily 3 since 1 is not prime. Now let us check that the equation can be solved for nn by substituting p=2p=2 and q=3q=3:
4+9=6n+1, 4+9=6 n+1,
from which n=2n=2. The only two solutions are therefore (2,3,2)(2,3,2) and (3,2,2)(3,2,2).

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 translated into English from it; metadata (topic, difficulty) added by this project.