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"
 
(10 intermediate revisions by 2 users not shown)
Line 2: Line 2:
 
Find all pairs of primes <math>(p,q)</math> for which <math>p-q</math> and <math>pq-q</math> are both perfect squares.
 
Find all pairs of primes <math>(p,q)</math> for which <math>p-q</math> and <math>pq-q</math> are both perfect squares.
  
−
==Solution==
+
==Solution 1==
 +
We first consider the case where one of <math>p,q</math> is even. If <math>p=2</math>, <math>p-q=0</math> and <math>pq-q=2</math> which doesn't satisfy the problem restraints. If <math>q=2</math>, we can set <math>p-2=x^2</math> and <math>2p-2=y^2</math> giving us <math>p=y^2-x^2=(y+x)(y-x)</math>. This forces <math>y-x=1</math> so <math>p=2x+1\rightarrow 2x+1=x^2+2 \rightarrow x=1</math> giving us the solution <math>(p,q)=(3,2)</math>.
  
−
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>.
+
Now assume that <math>p,q</math> are both odd primes. Set <math>p-q=x^2</math> and <math>pq-q=y^2</math> so <math>(pq-q)-(p-q)=y^2-x^2 \rightarrow p(q-1)</math> <math>=(y+x)(y-x)</math>. Since <math>y+x>y-x</math>, <math>p | (x+y)</math>. Note that <math>q-1</math> is an even integer and since <math>y+x</math> and <math>y-x</math> have the same parity, they both must be even. Therefore, <math>x+y=pk</math> for some positive even integer <math>k</math>. On the other hand, <math>p>p-q=x^2 \rightarrow p>x</math> and <math>p^2-p>pq-q=y^2 \rightarrow p>y</math>. Therefore, <math>2p>x+y</math> so <math>x+y=p</math>, giving us a contradiction.
  
  
−
<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>.
+
Therefore, the only solution to this problem is <math>(p,q)=(3,2)</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,
+
~BennettHuang
  
−
<math>
+
==See Also==
−
\left\{ \begin{array}{rcr}
+
{{USAJMO newbox|year=2022|num-b=4|num-a=6}}
−
b+a = & 2pn \\
+
{{MAA Notice}}
−
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)
 

Latest revision as of 19:04, 6 October 2023

Problem

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

Solution 1

We first consider the case where one of $p,q$ is even. If $p=2$, $p-q=0$ and $pq-q=2$ which doesn't satisfy the problem restraints. If $q=2$, we can set $p-2=x^2$ and $2p-2=y^2$ giving us $p=y^2-x^2=(y+x)(y-x)$. This forces $y-x=1$ so $p=2x+1\rightarrow 2x+1=x^2+2 \rightarrow x=1$ giving us the solution $(p,q)=(3,2)$.


Now assume that $p,q$ are both odd primes. Set $p-q=x^2$ and $pq-q=y^2$ so $(pq-q)-(p-q)=y^2-x^2 \rightarrow p(q-1)$ $=(y+x)(y-x)$. Since $y+x>y-x$, $p | (x+y)$. Note that $q-1$ is an even integer and since $y+x$ and $y-x$ have the same parity, they both must be even. Therefore, $x+y=pk$ for some positive even integer $k$. On the other hand, $p>p-q=x^2 \rightarrow p>x$ and $p^2-p>pq-q=y^2 \rightarrow p>y$. Therefore, $2p>x+y$ so $x+y=p$, giving us a contradiction.


Therefore, the only solution to this problem is $(p,q)=(3,2)$.


~BennettHuang

See Also

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

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