Olympiad Maths Prep

Library / /6 of 33

Number theory Difficulty 5.7 AIME, harder Prove it Belarus

Solve the equation p3q3=pq31p^3 - q^3 = pq^3 - 1 in primes p,qp, q.

Solution

Answer: q=7q = 7, p=19p = 19.

Note that qpq \le p, otherwise LHS <0< 0, RHS >0> 0. We have
p3q3=pq31p3+1=pq3+q3(p+1)(p2p+1)=q3(p+1)p(p1)=q31p(p1)=(q1)(q2+q+1). \begin{aligned} p^3 - q^3 &= pq^3 - 1 \Leftrightarrow p^3 + 1 = pq^3 + q^3 \\ &\Leftrightarrow (p+1)(p^2-p+1) = q^3(p+1) \\ &\Leftrightarrow p(p-1) = q^3 - 1 \\ &\Leftrightarrow p(p-1) = (q-1)(q^2+q+1). \end{aligned}
Since p(p1)pp(p-1) \nmid p, we have (q1)(q2+q+1)p(q-1)(q^2+q+1) \nmid p. But q1pq-1 \nmid p since q1<pq-1 < p, so q2+q+1pq^2+q+1 \nmid p, i.e., q2+q+1=kpq^2+q+1 = kp, kNk \in \mathbb{N}. Therefore
p(p1)=(q1)kpp1=k(q1)p=k(q1)+1. p(p-1) = (q-1)kp \Leftrightarrow p-1 = k(q-1) \Leftrightarrow p = k(q-1)+1.
Then
q2+q+1=kpq2+q+1=k2(q1)+k.(1) q^2 + q + 1 = kp \Leftrightarrow q^2 + q + 1 = k^2(q - 1) + k. \quad (1)
If k>3k > 3 we have
q2+q+1=k2(q1)+k    (q1)(q+2)+3=k2(q1)+k    (q1)(q+2)k2(q1)=k3. \begin{aligned} q^2 + q + 1 = k^2(q - 1) + k &\implies (q - 1)(q + 2) + 3 = k^2(q - 1) + k \\ &\implies (q - 1)(q + 2) - k^2(q - 1) = k - 3. \end{aligned}
Hence,
(k3)(q1)    kq1+3=q+2    (q1)(q+2)=k2(q1)+k3(q+2)2(q1)+q1>(q1)(q+2),which is impossible. So, we have no solutions when k>3. It remains toconsider three cases: k=1,2,3. \begin{gathered} (k-3) \mid (q-1) \implies k \ge q-1+3=q+2 \implies \\ (q-1)(q+2) = k^2(q-1) + k - 3 \ge (q+2)^2(q-1) + q - 1 > (q-1)(q+2), \\ \text{which is impossible. So, we have no solutions when } k > 3. \text{ It remains to} \\ \text{consider three cases: } k=1,2,3. \end{gathered}
If k=1k=1 from (1) we have q2+q+1=qq^2 + q + 1 = q. Hence q2+1=0q^2 + 1 = 0, which is impossible.

If k=2k=2 we have q2+q+1=4(q1)+2q^2 + q + 1 = 4(q - 1) + 2, which gives q23q+3=0q^2 - 3q + 3 = 0. It is easy to see that this equation has no real solution.

If k=3k=3 from (1) we have
q2+q+1=9(q1)+3q28q+7=0. q^2 + q + 1 = 9(q - 1) + 3 \Leftrightarrow q^2 - 8q + 7 = 0.
It is easy to see that either q=1q=1 or q=7q=7. But 1 is not prime, so q=7q=7, then p=3(q1)+1=19p=3(q-1)+1=19.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.