Maths Olympiad Prep

Library / /8 of 14

Number theory Difficulty 7.7 National Olympiad, round 2 Prove it European Girls' Mathematical Olympiad (EGMO)

Problem:

The numbers pp and qq are prime and satisfy
pp+1+q+1q=2nn+2 \frac{p}{p+1}+\frac{q+1}{q}=\frac{2 n}{n+2}
for some positive integer nn. Find all possible values of qpq-p.

Solution

Solution:

Rearranging the equation, 2qn(p+1)=(n+2)(2pq+p+q+1)2 q n(p+1) = (n+2)(2 p q + p + q + 1). The left hand side is even, so either n+2n+2 or p+q+1p+q+1 is even, so either p=2p=2 or q=2q=2 since pp and qq are prime, or nn is even.

If p=2p=2, 6qn=(n+2)(5q+3)6 q n = (n+2)(5 q + 3), so (q3)(n10)=36(q-3)(n-10) = 36. Considering the divisors of 3636 for which qq is prime, we find the possible solutions (p,q,n)(p, q, n) in this case are (2,5,28)(2,5,28) and (2,7,19)(2,7,19) (both of which satisfy the equation).

If q=2q=2, 4n(p+1)=(n+2)(5p+3)4 n(p+1) = (n+2)(5 p + 3), so n=pn+10p+6n = p n + 10 p + 6, a contradiction since n<pnn < p n, so there is no solution with q=2q=2.

Finally, suppose that n=2kn=2 k is even. We may suppose also that pp and qq are odd primes. The equation becomes 2kq(p+1)=(k+1)(2pq+p+q+1)2 k q(p+1) = (k+1)(2 p q + p + q + 1). The left hand side is even and 2pq+p+q+12 p q + p + q + 1 is odd, so k+1k+1 is even, so k=2+1k = 2 \ell + 1 is odd. We now have
q(p+1)(2+1)=(+1)(2pq+p+q+1) q(p+1)(2 \ell + 1) = (\ell + 1)(2 p q + p + q + 1)
or equivalently
q(p+1)=(+1)(pq+p+1) \ell q(p+1) = (\ell + 1)(p q + p + 1)
Note that qpq+p+1q \mid p q + p + 1 if and only if qp+1q \mid p+1. Furthermore, because (p,p+1)=1(p, p+1) = 1 and qq is prime, (p+1,pq+p+1)=(p+1,pq)=(p+1,q)>1(p+1, p q + p + 1) = (p+1, p q) = (p+1, q) > 1 if and only if qp+1q \mid p+1.

Since (,+1)=1(\ell, \ell+1) = 1, we see that, if qp+1q \nmid p+1, then =pq+p+1\ell = p q + p + 1 and +1=q(p+1)\ell + 1 = q(p+1), so q=p+2q = p+2 (and (p,p+2,2(2p2+6p+3))(p, p+2, 2(2 p^{2} + 6 p + 3)) satisfies the original equation). In the contrary case, suppose p+1=rqp+1 = r q, so (p+1)=(+1)(p+r)\ell(p+1) = (\ell+1)(p+r), a contradiction since <+1\ell < \ell+1 and p+1p+rp+1 \leq p+r.

Thus the possible values of qpq-p are 2,32, 3 and 55.

Solution 2:

Subtracting 22 and multiplying by 1-1, the condition is equivalent to
1p+11q=4n+2 \frac{1}{p+1} - \frac{1}{q} = \frac{4}{n+2}
Thus q>p+1q > p+1. Rearranging,
qp1=4(p+1)qn+2 q-p-1 = \frac{4(p+1)q}{n+2}
The expression on the right is a positive integer, and qq must cancel into n+2n+2 else qq would divide p+1<qp+1 < q. Let (n+2)/q=u(n+2)/q = u a positive integer.

So
qp1=4(p+1)u q-p-1 = \frac{4(p+1)}{u}
uqu(p+1)=4(p+1) u q - u(p+1) = 4(p+1)
so p+1p+1 divides uqu q. However, qq is prime and p+1<qp+1 < q, therefore p+1p+1 divides uu. Let vv be the integer u/(p+1)u/(p+1). Now
qp=1+4v{2,3,5} q-p = 1 + \frac{4}{v} \in \{2,3,5\}
All three cases can occur, where (p,q,n)(p, q, n) is (3,5,78)(3,5,78), (2,5,28)(2,5,28) or (2,7,19)(2,7,19). Note that all pairs of twin primes q=p+2q = p+2 yield solutions (p,p+2,2(2p2+6p+3))(p, p+2, 2(2 p^{2} + 6 p + 3)).

Solution 3:

Subtract 22 from both sides to get
1p+11q=4n+2 \frac{1}{p+1} - \frac{1}{q} = \frac{4}{n+2}
From this, since nn is positive, we have that q>p+1q > p+1. Therefore qq and p+1p+1 are coprime, since qq is prime.

Group the terms on the LHS to get
qp1q(p+1)=4n+2 \frac{q-p-1}{q(p+1)} = \frac{4}{n+2}
Now (q,qp1)=(q,p+1)=1(q, q-p-1) = (q, p+1) = 1 and (p+1,qp1)=(p+1,q)=1(p+1, q-p-1) = (p+1, q) = 1 so the fraction on the left is in lowest terms. Therefore the numerator must divide the numerator on the right, which is 44. Since qp1q-p-1 is positive, it must be 1,21, 2 or 44, so that qpq-p must be 2,32, 3 or 55. All of these can be attained, by (p,q,n)=(3,5,78)(p, q, n) = (3,5,78), (2,5,28)(2,5,28) and (2,7,19)(2,7,19) respectively.

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.