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

Difference between revisions of "2022 USAJMO Problems/Problem 5"

(→‎Problem)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
 +
 +
Let <math>p-q = a^2</math>, <math>pq - q = b^2</math>, where <math>a, b</math> are positive integers. <math>b^2 - a^2 = pq - q - (p-q) = pq -p</math>. So,
 +
<cmath> b^2 - a^2 = p(q-1) \tag{1}</cmath>
 +
 +
<math>\bullet</math> For <math>q=2</math>, <math>p = b^2 - a^2 = (b-a)(b+a)</math>. Then <math>b-a=1</math> and <math>b+a=p</math>. <math>a=\dfrac{p-1}{2}</math> and <math>p-q = a^2</math>. Thus, <math>p - 2 = \left( \dfrac{p-1}{2} \right)^2 \implies p^2 - 6p + 9 = 0</math> and we find <math>p=3</math>. Hence <math>(p,q) = (3,2)</math>.
 +
 +
 +
<math>\bullet</math> For <math>q=4k+3</math>, (<math>k\geq 0</math> integer), by <math>(1)</math>, <math>p(4k+2) = b^2 - a^2</math>. Let's examine in <math>\mod 4</math>, <math>b^2 - a^2 \equiv 2 \pmod{4}</math>. But we know that <math>b^2 - a^2 \equiv 0, 1 \text{ or } 3 \pmod{4}</math>. This is a contradiction and no solution for <math>q = 4k + 3</math>.
 +
 +
 +
<math>\bullet</math> For <math>q=4k+1</math>, (<math>k > 0</math> integer), by <math>(1)</math>, <math>p(4k) = b^2 - a^2</math>. Let <math>k=m\cdot n</math>, where <math>m\geq n \geq 1</math> and <math>m, n</math> are integers. Since <math>p>q</math>, we see <math>p>4k</math>. Thus, by <math>(1)</math>, <math> (b-a)(b+a) = 4p\cdot m \cdot n</math>. <math>b-a</math> and <math>b+a</math> are same parity and  <math>4p\cdot m \cdot n</math> is even integer. So, <math>b-a</math> and <math>b+a</math> are both even integers. Therefore,
 +
 +
<math>
 +
\left\{ \begin{array}{rcr}
 +
b+a =  & 2pn \\
 +
b-a =  & 2m
 +
\end{array} \right.
 +
</math>
 +
or
 +
<math>
 +
\left\{ \begin{array}{rcr}
 +
b+a =  & 2pm \\
 +
b-a =  & 2n
 +
\end{array} \right.
 +
</math>
 +
Therefore, <math>a=pn - m</math> or <math>a = pm - n</math>. For each case, <math>p-q = p - 4mn - 1 < a</math>. But <math>p-q = a^2</math>, this gives a contradiction. No solution for <math>q = 4k + 1</math>.
 +
 +
 +
We conclude that the only solution is <math>(p,q) = (3,2)</math>.
 +
 +
(Lokman GÖKÇE)

Revision as of 04:08, 26 April 2022

Problem

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

Solution

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)

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2022_USAJMO_Problems/Problem_5&oldid=173604"