Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2022 USAMO Problems/Problem 4

Problem

Find all pairs of primes $(p, q)$ for which $p-q$ and $pq-q$ are both perfect squares.

Solution 1

Since $q(p-1)$ is a perfect square and $q$ is prime, we should have $p - 1 = qb^2$ for some positive integer $b$. Let $a^2 = p - q$. Therefore, $q = p - a^2$, and substituting that into the $p - 1 = qb^2$ and solving for $p$ gives \[p = \frac{a^2b^2 - 1}{b^2 - 1} = \frac{(ab - 1)(ab + 1)}{b^2 - 1}.\] Notice that we also have \[p = \frac{a^2b^2 - 1}{b^2 - 1} = a^2 + \frac{a^2 - 1}{b^2 - 1}\] and so $b^2 - 1 | a^2 - 1$. We run through the cases

  • $a = 1$: Then $p - q = 1$ so $(p, q) = (3, 2)$, which works.
  • $a = b$: This means $p = a^2 + 1$, so $q = 1$, a contradiction.
  • $a > b$: This means that $b^2 - 1 < ab - 1$. Since $b^2 - 1$ can be split up into two factors $F_1, F_2$ such that $F_1 | ab - 1$ and $F_2 | ab + 1$, we get

\[p = \frac{ab - 1}{F_1} \cdot \frac{ab + 1}{F_2}\] and each factor is greater than $1$, contradicting the primality of $p$.

Thus, the only solution is $(p, q) = (3, 2)$.

Solution 2

Let $p-q = a^2$, $pq - q = b^2$, where $a, b$ are positive integers. $b^2 - a^2 = pq - q - (p-q) = pq -p$. So, \[b^2 - a^2 = p(q-1) \tag{1}\]

$\bullet$ For $q=2$, $p = b^2 - a^2 = (b-a)(b+a)$. Then $b-a=1$ and $b+a=p$. $a=\dfrac{p-1}{2}$ and $p-q = a^2$. Thus, $p - 2 = \left( \dfrac{p-1}{2} \right)^2 \implies p^2 - 6p + 9 = 0$ and we find $p=3$. Hence $(p,q) = (3,2)$.


$\bullet$ For $q=4k+3$, ($k\geq 0$ integer), by $(1)$, $p(4k+2) = b^2 - a^2$. Let's examine in $\mod 4$, $b^2 - a^2 \equiv 2 \pmod{4}$. But we know that $b^2 - a^2 \equiv 0, 1 \text{ or } 3 \pmod{4}$. This is a contradiction and no solution for $q = 4k + 3$.


$\bullet$ For $q=4k+1$, ($k > 0$ integer), by $(1)$, $p(4k) = b^2 - a^2$. Let $k=m\cdot n$, where $m\geq n \geq 1$ and $m, n$ are integers. Since $p>q$, we see $p>4k$. Thus, by $(1)$, $(b-a)(b+a) = 4p\cdot m \cdot n$. $b-a$ and $b+a$ are same parity and $4p\cdot m \cdot n$ is even integer. So, $b-a$ and $b+a$ are both even integers. Therefore,

$\left\{ \begin{array}{rcr} b+a = & 2pn \\ b-a = & 2m \end{array} \right.$ or $\left\{ \begin{array}{rcr} b+a = & 2pm \\ b-a = & 2n \end{array} \right.$ Therefore, $a=pn - m$ or $a = pm - n$. For each case, $p-q = p - 4mn - 1 < a$. But $p-q = a^2$, this gives a contradiction. No solution for $q = 4k + 1$.


We conclude that the only solution is $(p,q) = (3,2)$.

(Lokman GÖKÇE)

Solution 3

We claim that the only solution is $(p,q) = (3,2)$. First, this clearly works, since $3-2=1^2$ and $3\cdot2-2=2^2$.

Start as in Solution 2 - assign positive integers $m, n,$ such that $p-q=m^2$ and $pq-q=n^2.$ Then, $pq-p=n^2-m^2,$ or $p(q-1)=(n-m)(n+m).$

First, $p=q$ is impossible, since $p^2-p = p(p-1)$ is not a perfect square. Now notice that $m<p$ and $n<\max(p,q-1).$ But $p-q>0,$ so $p\geq q-1.$ Now, $m, n < p.$

Therefore, $n-m$ can't ever be a factor of $p,$ and $n+m<2p,$ so $n+m=p.$ Then, $n-m=q-1,$ so $p-q=2m-1.$ But $p-q=m^2,$ so $m^2=2m-1,$ or $m=1.$ Therefore, one of $p$ and $q$ must be $2$ (and $1$ is not a prime).

Thus, we conclude that our claim is true.

(grape1984)

See also

2022 USAMO (Problems • Resources)
Preceded by
Problem 3 		Followed by
Problem 5
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2022_USAMO_Problems/Problem_4&oldid=254772"