Maths Olympiad Prep

Library / /66 of 224

Number theory Difficulty 5.6 AIME, harder Prove it Belarus

Solve the equation in prime numbers pp and qq: q3=p2p+1q^3 = p^2 - p + 1.

Solutions — 2

Solution 1

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

(Solution of E. Dauhiala, B. Gilevich, A. Zhuk, A. Semchankau.) We have
q3=p2p+1(q1)(q2+q+1)=p(p1).(1) q^3 = p^2 - p + 1 \Leftrightarrow (q-1)(q^2+q+1) = p(p-1). \quad (1)
If (q1)p(q-1) \nmid p, then qp+1q \ge p+1, so q3>p2p+1q^3 > p^2 - p + 1.
Hence, (q2+q+1)p(q^2+q+1) \nmid p, i.e.
q2+q+1=kp(2) q^2 + q + 1 = k p \quad (2)
for some kNk \in \mathbb{N}. It follows that k(q1)=p1k(q-1) = p-1, or p=kqk+1p = kq - k + 1. Substituting this expression in (2) we obtain q2+(1k2)q+(k2k+1)=0q^2 + (1-k^2)q + (k^2-k+1) = 0. The discriminant of this quadratic on qq equation
D=(k21)2(4k2k+1)=k46k2+4k3 D = (k^2 - 1)^2 - (4k^2 - k + 1) = k^4 - 6k^2 + 4k - 3
must be a perfect square. But it is easy to check that
(k23)2<k46k2+4k3<(k21)2for any k>3. (k^2 - 3)^2 < k^4 - 6k^2 + 4k - 3 < (k^2 - 1)^2 \quad \text{for any } k > 3.
Moreover, the equation k46k2+4k3=(k22)2k^4 - 6k^2 + 4k - 3 = (k^2 - 2)^2 has no solutions.
Hence, k3k \le 3. For k=1k = 1 we have D=4D = -4, and for k=2k = 2 we have D=3D = -3, which is impossible. For k=3k = 3 we obtain D=62D = 6^2, so q=(8±6)/2q = (8 \pm 6)/2. Thus q=7q = 7 and p=k(q1)+1=19p = k(q-1) + 1 = 19. It remains to note the primes p=19,q=7p = 19, q = 7 do satisfy the equation.

Solution 2

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

We have
q3=p2p+1(q1)(q2+q+1)=p(p1).(1) q^3 = p^2 - p + 1 \Leftrightarrow (q-1)(q^2 + q + 1) = p(p-1). \quad (1)
If (q1)p(q-1) \nmid p, then qp+1q \ge p+1, so q3>p2p+1q^3 > p^2 - p + 1.
Hence, (q2+q+1)p(q^2 + q + 1) \nmid p, i.e.
q2+q+1=kp(2) q^2 + q + 1 = k p \quad (2)
for some kNk \in \mathbb{N}. It follows that k(q1)=p1k(q-1) = p-1, or p=kqk+1p = kq - k + 1. Substituting this expression in (2) we obtain q2+(1k2)q+(k2k+1)=0q^2 + (1-k^2)q + (k^2-k+1) = 0. The discriminant of this quadratic on qq equation
D=(k21)2(4k2k+1)=k46k2+4k3 D = (k^2 - 1)^2 - (4k^2 - k + 1) = k^4 - 6k^2 + 4k - 3
must be a perfect square. But it is easy to check that
(k23)2<k46k2+4k3<(k21)2for any k>3. (k^2 - 3)^2 < k^4 - 6k^2 + 4k - 3 < (k^2 - 1)^2 \quad \text{for any } k > 3.
Moreover, the equation k46k2+4k3=(k22)2k^4 - 6k^2 + 4k - 3 = (k^2 - 2)^2 has no solutions.
Hence, k3k \le 3. For k=1k = 1 we have D=4D = -4, and for k=2k = 2 we have D=3D = -3, which is impossible. For k=3k = 3 we obtain D=62D = 6^2, so q=(8±6)/2q = (8 \pm 6)/2. Thus q=7q = 7 and p=k(q1)+1=19p = k(q-1) + 1 = 19. It remains to note the primes p=19p = 19, q=7q = 7 do satisfy the equation.

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.