Maths Olympiad Prep

Library / /99 of 520

Number theory Difficulty 5.7 AIME, harder Find the answer

Find all pairs of prime numbers (p,q)(p, q) for which

p(p2p1)=q(2q+3) p\left(p^{2}-p-1\right)=q(2 q+3)

A number or a short expression. Spacing and $ signs are ignored.

Solution

Answer: the only solution is (p,q)=(13,31)(p, q)=(13,31).
If p=qp=q, then it must also hold that p2p1=2q+3=2p+3p^{2}-p-1=2 q+3=2 p+3. This can be factored as (p4)(p+1)=0(p-4)(p+1)=0. Since 4 and -1 are not prime numbers, this does not yield any solutions.

In the other case, we have p2q+3p \mid 2 q+3 and qp2p1q \mid p^{2}-p-1. Since 2q+32 q+3 and p2p1p^{2}-p-1 are positive, it follows that p2q+3p \leq 2 q+3 and qp2p1q \leq p^{2}-p-1. To find a sharper lower bound for pp, we multiply the two relations

pq(2q+3)(p2p1)2qp22qp2q+3(p2p1)3(p2p1)2q, \begin{aligned} p q & \mid(2 q+3)\left(p^{2}-p-1\right) \\ & \mid 2 q p^{2}-2 q p-2 q+3\left(p^{2}-p-1\right) \\ & \mid 3\left(p^{2}-p-1\right)-2 q, \end{aligned}

where we have discarded terms with a factor of pqp q. Note now that 3(p2p1)2q3\left(p^{2}-p-1\right)-2 q \geq 3q2q=q>03 q-2 q=q>0. This means that the above divisibility relation leads to

pq3(p2p1)2q=3p23p(2q+3)3p23pp=3p24p. \begin{aligned} p q & \leq 3\left(p^{2}-p-1\right)-2 q \\ & =3 p^{2}-3 p-(2 q+3) \\ & \leq 3 p^{2}-3 p-p \\ & =3 p^{2}-4 p . \end{aligned}

If we move 4p4 p to the other side and divide by pp, we find that q+43pq+4 \leq 3 p, or

2q+36<q+43p \frac{2 q+3}{6}<\frac{q+4}{3} \leq p

Since pp is a divisor of 2q+32 q+3, we deduce that 2q+3=kp2 q+3=k p with k{1,2,3,4,5}k \in\{1,2,3,4,5\}. If k=1k=1, then we have 2q+3=p2 q+3=p and thus also q=p2p1q=p^{2}-p-1. But then it would hold that p=2q+3=2(p2p1)+3=2p22p+1p=2 q+3=2\left(p^{2}-p-1\right)+3=2 p^{2}-2 p+1. This can be factored as (2p1)(p1)=0(2 p-1)(p-1)=0, which has no solutions with pp prime. If k=2k=2 or k=4k=4, then kpk p is even. But 2q+32 q+3 is odd, so these cases are ruled out. If k=3k=3, then from 2q+3=3p2 q+3=3 p it follows that qq must be a multiple of 3. Since qq is prime, we then have q=3q=3, and thus also p=(2q+3)/3=3p=(2 q+3) / 3=3. Checking shows that this is not a solution to the original equation.

The last case is k=5k=5. Then we have 5p=2q+35 p=2 q+3 and from the original equation, we have 5q=p2p15 q=p^{2}-p-1. If we substitute this, we get 25p=5(2q+3)=25 p=5(2 q+3)= 2(p2p1)+15=2p22p+132\left(p^{2}-p-1\right)+15=2 p^{2}-2 p+13. This can be factored as (p13)(2p1)=0(p-13)(2 p-1)=0. This gives the possible solution p=13p=13 with q=(5p3)/2=31q=(5 p-3) / 2=31. We check that (p,q)=(13,31)(p, q)=(13,31) is indeed a solution to the problem.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.