Olympiad Maths Prep

Track / Stage 5 / 303 of 400 #903 of 2000

Problem 903

AIME late
Number theory Difficulty 5.7 Find the answer

2. Find all such triples of prime numbers p,qp, q and rr, that pq=8r1+1\frac{p}{q}=\frac{8}{r-1}+1.

Official solution

Answer: (7,3,7);(5,3,13);(3,2,17)(7,3,7); (5,3,13); (3,2,17).

First solution. Rewrite the relation as

8q=(pq)(r1) 8 q=(p-q)(r-1)

If q=2q=2, it becomes 16=(p2)(r1)16=(p-2)(r-1). Then p2p-2 is a power of two, so p=3p=3 and r=17r=17. If r=2r=2, the relation ()(*) becomes 8q=pq8 q=p-q, from which p=9qp=9 q, which is impossible. We will further assume that qq and rr are odd prime numbers. But then the prime number pp is also odd, otherwise the left side of ()(*) is negative. Therefore, r1r-1 and pqp-q are even numbers, so pq=2p-q=2 and r1=4qr-1=4 q or pq=4p-q=4 and r1=2qr-1=2 q. If q=3q=3, in the first case p=5p=5 and r=13r=13, and in the second case p=r=7p=r=7. Thus, we can assume that q>3q>3. Consider the first case. Since pp and qq are not divisible by 3 and p=q+2p=q+2, qq has the form 3k+23 k+2, but then r=4q+1=12k+9r=4 q+1=12 k+9, which is impossible. Consider the second case. Since pp and qq are not divisible by 3 and p=q+4p=q+4, qq has the form 3k+13 k+1, but then r=2q+1=6k+3r=2 q+1=6 k+3, which is also impossible.

Second solution. From the condition, it follows that p>qp>q. Multiply by the denominators and rewrite the relation as 7q+p=(pq)r7 q+p=(p-q) r. From this, in particular, we get that 7q+p7 q+p is divisible by pqp-q. Therefore, 8q=(7q+p)(pq)8 q=(7 q+p)-(p-q) is also divisible by pqp-q. On the other hand, 8p=(7q+p)+7(pq)8 p=(7 q+p)+7(p-q) is also divisible by pqp-q. Thus, pqp-q divides the greatest common divisor of the numbers 8p8 p and 8q8 q, but this divisor is 8. Therefore, only three cases are possible: pq=1,pq=2,pq=4p-q=1, p-q=2, p-q=4 and pq=8p-q=8. Note immediately that in the last three cases pq+24p \geqslant q+2 \geqslant 4 and, in particular, pp is not divisible by three.

The first case is possible only when p=3p=3 and q=2q=2, and then r=17r=17, which is the first solution.

In the second case, pq=2p-q=2 and then r=12(7q+p)=4q+1=4p7r=\frac{1}{2}(7 q+p)=4 q+1=4 p-7. If rr gives a remainder of 2 when divided by three, then pp will be divisible by three, which is impossible. If rr gives a remainder of 1 when divided by three, then qq will be divisible by three and, therefore, q=3,p=5q=3, p=5 and r=5r=5, which gives the second solution.

In the third case, pq=4p-q=4 and then r=14(7q+p)=2q+1=2p7r=\frac{1}{4}(7 q+p)=2 q+1=2 p-7. If rr gives a remainder of 2 when divided by three, then pp will be divisible by three, which is impossible. If rr gives a remainder of 1 when divided by three, then qq will be divisible by three and, therefore, q=3,p=7q=3, p=7 and r=7r=7, which is the third solution.

In the fourth case, pq=8p-q=8 and then r=18(7q+p)=q+1=p7r=\frac{1}{8}(7 q+p)=q+1=p-7. If rr gives a remainder of 2 when divided by three, then pp will be divisible by three, which is impossible. If rr gives a remainder of 1 when divided by three, then qq will be divisible by three and, therefore, q=3q=3 and r=4r=4, which is impossible.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.