Maths Olympiad Prep

Library / /9 of 22

Number theory Difficulty 8.0 National Olympiad, round 2 Prove it Germany

Find all quadruples of positive integers (m,n,p,qm, n, p, q) with the property
pmqn=(p+q)2+1 p^{m} q^{n} = (p+q)^{2} + 1

Solutions — 2

Solution 1

1. Lemma: If k,l,ak, l, a are positive integers with a=(k2+l2+1)/(kl)a = (k^{2} + l^{2} + 1)/(k l), then a=3a = 3 follows.

Proof of the lemma: For a given value of aa we consider a pair (k,l)(k, l) with k2+l2+1=aklk^{2} + l^{2} + 1 = a k l and minimal sum k+lk + l among all such pairs. Without loss of generality let klk \leq l.

First suppose k<lk < l. By assumption, kk satisfies the quadratic equation
x2+l2+1axl=0, x^{2} + l^{2} + 1 - a x l = 0,
for whose 2nd solution kk' it follows by Vieta's theorem that: k+k=alk + k' = a l and kk=l2+1k k' = l^{2} + 1. Thus k=alkk' = a l - k is an integer, it is positive because k=(l2+1)/kk' = (l^{2} + 1)/k, and since kl+1k \geq l + 1 and kk=l2+1<(l+1)2k k' = l^{2} + 1 < (l + 1)^{2} we have klk' \leq l, so (l,k)(l, k') is a pair with smaller sum l+k<k+ll + k' < k + l, contrary to the choice of (k,l)(k, l).

Hence k=lk = l holds, so k2(a2)=1k^{2}(a - 2) = 1, from which k=1k = 1 and a=3a = 3 follow.

Since m1m \geq 1 and n1n \geq 1, the expression pm1qn1=(p2+q2+1)/(pq)+2p^{m-1} q^{n-1} = (p^{2} + q^{2} + 1)/(p q) + 2 is an integer, so by the lemma pm1qn1=5p^{m-1} q^{n-1} = 5 and thus pm1=1,qn1=5p^{m-1} = 1, q^{n-1} = 5 or pm1=5,qn1=1p^{m-1} = 5, q^{n-1} = 1.

In the first case n=2n = 2 and q=5q = 5; pp satisfies equation (1) for l=5,a=3l = 5, a = 3 with solutions 22 and 1313, from pm1=1p^{m-1} = 1 it follows in each case that m=1m = 1, and by substitution one confirms the solution quadruples (1,2,2,5)(1, 2, 2, 5) and (1,2,13,5)(1, 2, 13, 5). The second case yields correspondingly (2,1,5,2)(2, 1, 5, 2) and (2,1,5,13)(2, 1, 5, 13).

Solution 2

All summands of the original equation except for q2+1q^{2} + 1 are multiples of pp, hence pq2+1p \mid q^{2} + 1 holds. Thus the cases q=1,2,,6q = 1, 2, \ldots, 6 can be treated by direct checking, yielding the solution quadruples from Solution 1. For pq7p \geq q \geq 7 (analogously: pp7p \geq p \geq 7) there are no solutions:

Case 1: m>1m > 1: Then pmqnp2q>6p2(p+q)2+1p^{m} q^{n} \geq p^{2} q > 6 p^{2} \geq (p + q)^{2} + 1.

Case 2: n>2n > 2: Then, because pq2+1p \leq q^{2} + 1: pmqnpq3p2qpq>5p2>(p+q)2+1p^{m} q^{n} \geq p q^{3} \geq p^{2} q - p q > 5 p^{2} > (p + q)^{2} + 1.

Case 3: m=n=1m = n = 1: For this, p2+pq+q2+1=0p^{2} + p q + q^{2} + 1 = 0 would have to hold - impossible for p>0,q>0p > 0, q > 0.

Case 4: m=1,n=2m = 1, n = 2: The quadratic equation pq2=(p+q)2+1p q^{2} = (p + q)^{2} + 1 in pp has discriminant D=q44q34D = q^{4} - 4 q^{3} - 4, which for q7q \geq 7 lies between the consecutive square numbers (q22q3)2(q^{2} - 2q - 3)^{2} and (q22q2)2(q^{2} - 2q - 2)^{2}, so D\sqrt{D}, and hence also pp, is not an integer.

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