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 q−pq-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 (q−3)(n−10)=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 q∣pq+p+1q \mid p q + p + 1 if and only if q∣p+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 q∣p+1q \mid p+1.

Since (ℓ,ℓ+1)=1(\ell, \ell+1) = 1, we see that, if q∤p+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+1≤p+rp+1 \leq p+r.

Thus the possible values of q−pq-p are 2,32, 3 and 55.

Solution 2:

Subtracting 22 and multiplying by −1-1, the condition is equivalent to
1p+1−1q=4n+2 \frac{1}{p+1} - \frac{1}{q} = \frac{4}{n+2}
Thus q>p+1q > p+1. Rearranging,
q−p−1=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
q−p−1=4(p+1)u q-p-1 = \frac{4(p+1)}{u}
uq−u(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
q−p=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+1−1q=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
q−p−1q(p+1)=4n+2 \frac{q-p-1}{q(p+1)} = \frac{4}{n+2}
Now (q,q−p−1)=(q,p+1)=1(q, q-p-1) = (q, p+1) = 1 and (p+1,q−p−1)=(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 q−p−1q-p-1 is positive, it must be 1,21, 2 or 44, so that q−pq-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.