Find all pairs of primes $(p, q)$ for which $p-q$ and $pq-q$ are both perfect squares.
Problem
Source: USAMO 2022/4, JMO 2022/5
Tags: number theory, Diophantine equation, prime numbers, xtimmyGgettingflamed
24.03.2022 21:04
Ans (3,2). Subtract and factor by difference of squares. Then p must go into one of the two. Make cases and then do bounding.
24.03.2022 21:05
(3,2) was the only answer
24.03.2022 21:05
Also JMO 2022/5 For some reason this took me like 2 hours in contest and I got it with 20 minutes left. Unlike j2 I managed to finish the writeup in time The answer is $(3,2)$ only which works. It's easy to check that $q=2$ yields $p=3$, so henceforth suppose $q>2$, and thus $p\geq q+2$. Now let $p-q=a^2,pq-q=(bq)^2 \implies p=b^2q+1$. Substituting back, we get $$q=\frac{a^2-1}{b^2-1} \text{ and } p=\frac{a^2b^2-1}{b^2-1}=\frac{(ab+1)(ab-1)}{b^2-1}.$$Now, note that we have $b^2=\tfrac{p-1}{q}$, and $$p-q>\frac{p-1}{q} \iff pq-q^2>p-1 \iff p(q-1)>q^2-1 \iff p>q+1,$$which is true by our previous assumption, so $a>b$ (edit several months later: this is rather unnecessary if we just use the fact that $q>1$). Then, $ab+1>ab-1>b^2-1$, so we have $ab+1 \nmid b^2-1, ab-1 \nmid b^2-1$ (if $b=1$ then $p-1=q$ which contradicts $p \geq q+2$). Thus there exist $d_1,d_2 \neq 1$, neither dividing $b^2-1$, such that $d_1 \mid ab+1$ and $d_2 \mid ab-1$. Then $d_1d_2 \mid p$, which means $p$ is composite: absurd. $\blacksquare$
24.03.2022 21:05
This problem was proposed by me $ $:$ $D
24.03.2022 21:07
24.03.2022 21:07
Note that if $p-q=1$, then $(p,q)=(3,2)$ is the only option by mod 2. We claim that this is the only solution. Write $p-q=x^2$ and $pq-q=y^2$ where $x\geq 2$ and $y\geq 1$. Then, rearranging gives will edit in
24.03.2022 21:08
This just works right. We claim that the only pair of such primes is $(p, q)=(3, 2)$. Suppose $p-q=a^2$ and $pq-q=b^2$. Now subtracting these two, we have $$b^2-a^2 =p(q-1)$$Notice that $p>b$ and $pq-q<p^2$ which implies $a<\sqrt{p}$ and therefore $p \leq a+b < p+\sqrt{p}$, so clearly $p=a+b$ and $q=b-a+1$ which implies $a=1$ and the only consecutive primes are $3$ and $2$. $\blacksquare$ @VicKmath7 woops fixed it now, thanks!!
24.03.2022 21:09
The answer is $(3,2)$ only. Let $p-q=a^2, pq-q=b^2$. First, $b^2=q(p-1)$. This means either $p-1=q$ or $p-1\ge 4q$. If $p-1=q$ then $p=3,q=2$ is forced, and it works. From now on, assume $p>4q$. Observe $(b+a)(b-a)=b^2-a^2=p(q-1)$. Since $p>4q$, $p$ can only divide $b+a$. This means $\frac{b+a}{b-a}\ge \frac{p}{q-1}=4$ This means $b+a\ge 4b-4a$ so $5a\ge 3b$, or $\frac ba \le \frac 53$. Therefore, $q=\frac{pq-q^2}{p-q} < \frac{pq-q}{p-q} \le (\frac 53)^2$, so $q=2$. Now, note $a^2=p-2$ and $2b^2=p-1$. We have $a^2+b^2\equiv a^2-2b^2\equiv -1(\bmod\; 3)$, so $3\nmid ab$, so $3\mid p$, so $p=3$.
24.03.2022 21:09
The only pair is $\boxed{(3,2)}$. Let $pq-q=a^2. p-q=b^2$. Note that it's immediately implied that $p\ge q$; consequentially $pq-q<p^2\rightarrow a<p$. Also note that $p-q<p\rightarrow b<\sqrt{p}$. Note that $p(q-1)=a^2-b^2=(a+b)(a-b)$. Since $a-b<p$, $p$ necessarily divides $a+b$, and since $a+b< p+\sqrt{p}<2p$, $a+b=p$ and $a-b=q-1$. Adding the two equations together gives $$a=\frac{p+q-1}{2}$$ and since $a$ is an integer, one of $p,q$ must be even, or equal to $2$. Since $q\le p$, $q=2$ and $a-b=1$. We can solve $2(b^2+2)-2=(b+1)^2\rightarrow b=1, p=3$.
24.03.2022 21:13
let x^2=p-q and y^2=q(p-1), use difference of squares to find x+y=p and x-y=1-q. them simplify and set equal to (x+y)^2 to find that q=p-1 which means only (3,2) works. (will edit in full sol later)
24.03.2022 21:14
I did the same as Debayu except after getting $p=a+b$ I no-brained and let $p=\sqrt{p-q}+\sqrt{pq-q}$ and squared both sides and simplified multiple times to get $(q+1-p)^2=0$ and $p=q+1$ im sad now
24.03.2022 21:19
DebayuRMO wrote: This just works right. We claim that the only pair of such primes is $(p, q)=(3, 2)$. Suppose $p-q=a^2$ and $pq-q=b^2$. Now subtracting these two, we have $$b^2-a^2 =p(q-1)$$Notice that $p>b$ so clearly $p=a+b$ and $q=b-a+1$ which implies $a=1$ and the only consecutive primes are $3$ and $2$. $\blacksquare$ I am pretty sure you obtain only $p | a+b$ from $p(q-1)=(b-a)(b+a)$, not $p=a+b$, so you have to do a few more bounds as some of the other posters did.
24.03.2022 21:22
Does this work? We claim the answer is $\boxed{(3,2)}$. Case 1: $q=2$. Then let $p-2=a^2$ and $2p-2=2(p-1)=4b^2$. So we have \[p=(2p-2)-(p-2)=4b^2-a^2=(2b-a)(2b+a)\] Thus, $2b-a=1$ and $2b+a=p$. This implies $4b=p+1\implies b=\frac{p+1}{4}$. Then $a=\frac{p-1}{2}$. Now \[p-2=\frac{(p-1)^2}{4}\implies 4p-8=p^2-2p+1\implies p^2-6p+9=0\implies p=3\]$\blacksquare$ Case 2: $q>2$. Let $p-q=a^2$ and $pq-q=q(p-1)=q^2b^2$. Now $p-1=qb^2\implies p=qb^2+1$. We have \[(pq-q)-(p-q)=pq-p=p(q-1)=(qb-a)(qb+a)\] Since $p(q-1)$ and $qb+a$ are positive, $qb-a>0\implies qb>a$. Also, $p\mid (qb-a)(qb+a)$. Thus, $p\mid qb-a$ or $p\mid qb+a$. Note that $qb<qb^2+1=p$. We have $0<qb,a<p$, so if $p\mid qb-a$, then $qb-a=0$, a contradiction. Thus, $p\mid qb+a\implies qb+a=p\implies a=p-qb$. Now we have the equation \[p(q-1)=(qb-a)p\implies q-1=qb-a=qb-(p-qb)=2qb-p\] Note that \[2qb-p=2qb-(qb^2+1)=2qb-qb^2-1\] So \[q-1=2qb-qb^2-1\implies q=2qb-qb^2\implies 2b-b^2=1\implies b=1\] Then $q(p-1)=q^2\implies p-1=q\implies q=2$, a contradiction. $\blacksquare$
24.03.2022 21:24
hyxue wrote: I did the same as Debayu except after getting $p=a+b$ I no-brained and let $p=\sqrt{p-q}+\sqrt{pq-q}$ and squared both sides and simplified multiple times to get $(q+1-p)^2=0$ and $p=q+1$ im sad now same lol
24.03.2022 21:29
bruh i did some weird thing that was like set $p-q=a^2$ and $pq-q=b^2$ then subtracted to get $(b+a)(b-a)=p(q-1)$ AND THEN I WAS LIKE OK SO THEN WE DO SOME STUFF AND THEREFORE $p=(b+a), q-1=(b-a)$ or vice versa, and from both of these we get $a^2=1$ producing working pair of $(p,q)=(3,2).$ Then you do some stuff with when $1 \cdot pq-p = (b+a)(b-a)$ and ultimately result with (3,2) only pair (this is very scuffed)
24.03.2022 21:34
the way i did it after i got (ab-1)(ab+1)/(b^2-1) is a prime is show either ab-1 and ab+1 divide b^2-1 (this is true intuitively because if otherwise, there is "leftover" on both ab-1 and ab+1, so the expression cant be prime but u can do it rigorously with prime factorization) which implies conclusion since a > b
24.03.2022 21:36
I solved the case when $p$ and $q$ are odd primes using a pell equation and parity contradiction... can anyone confirm this works?
24.03.2022 21:42
Hopefully my original submission, attached here, is a 7 The only solution is $(p, q) = \boxed{(3, 2)}$. Obviously this works, as $p-q=1$ and $pq-q=4$. First, assume $p = q$. Then $q^2-q$ must be a perfect square; yet, $q>2$ so $$(q-1)^2 < q^2 - q < q^2,$$which is impossible. Henceforth assume $p \neq q$ and let $p = q + k^2$ for some positive integer $k$. Then, $q^2+qk^2 - q$ is a perfect square; in other words, there exists a positive integer $r$ such that $$q^2+qk^2 - q = q^2r^2 \iff q+k^2-1 = qr^2, q = \frac{k^2-1}{r^2-1}.$$As a result, $$p = \frac{k^2-1}{r^2-1} + k^2 = \frac{k^2r^2-1}{r^2-1} = \frac{(rk+1)(rk-1)}{r^2-1}.$$I claim that if $k, r \neq 1$, this implies either $rk+1 \mid r^2-1$ or $rk-1 \mid r^2-1$. Assume that neither are true, and let $a = \gcd(rk+1, r^2-1) \neq rk+1$, and $b = \frac{r^2-1}a$ which is an integer by definition of GCD. Next let $x = \frac{rk+1}a$ and $y = \frac{rk-1}b$. Because by definition, $\gcd(x, r^2-1) = 1$, it follows that $b \mid rk-1$ as well, so $y$ is an integer. Furthermore, by the assumption we have $x \neq 1$, and if $y=1$ then $\frac{r^2-1}a = kr-1$ which contradicts $rk-1 \nmid r^2-1$. As a result, $x, y > 1$. But now $$p(r^2-1) = abxy = xy(r^2-1),$$with $xy$ not prime. This is a contradiction. Now what remains is casework. If $rk-1 \mid r^2-1$, then $rk-1 \leq r^2-1$ which implies $k \leq r$. But $\frac{k^2-1}{r^2-1} \geq 2$, which is a contradiction. If $rk+1 \mid r^2-1$, then $rk+1 \leq r^2-1$. Obviously by similar logic to the first case, this is a contradiction. Thus we must have $k=r=1$, as one implies the other. This means that $p, q$ are primes that differ by exactly 1 in that order, so $(p, q) = (3, 2)$ is the only solution.
Attachments:
USAJMO_student_804_p5_1_page.pdf (55kb)
24.03.2022 21:44
So my humongous brain managed to miss (3, 2), and said there's no solutions. I'm so smart.
09.02.2024 20:33
My solution Take $p - q = a^2$, $pq - q = b^2$. Subtracting the two equations we have: $$pq - p = b^2 - a^2 \implies p(q - 1) = (b - a)(b + a)$$We know $p \geq a$, and $p \geq q \implies p > q - 1 \implies p > b$. Therefore, $b - a < p, b + a < 2p$. We know: $$p \mid (b - a)(b + a) \; \text{since $b - a < p$ we have} \; p \mid b + a \implies b + a = p$$This also means $b - a = q - 1$, and since $(2, 2)$ doesn't work, $p$ is odd, which means $2 \nmid b + a \implies 2 \nmid b - a \implies 2 \mid b - a + 1 \implies 2 \mid q$. Since $q$ is prime, $q = 2$. This means that $b - a = 1 \implies b = a + 1 \implies p = 2a + 1 \implies 2a - 1 = a^2 \implies a = 1 \implies p = 3 \implies b = 2$. So we are done.
05.03.2024 22:28
Cute! The answer is $\boxed{(3,2)}$, which clearly works. Denote \begin{align*} pq-q&=a^2\\ p-q&=b^2. \end{align*}Subtracting gives $p(q-1)=(a-b)(a+b)$. As $p>q-1$, we need $p\mid(a+b)$. Since $pq-q<p^2$, we actually have $a=p-b$. Substituting yields \begin{align*} pq-q=(p-b)^2&=p^2-2bp+(p-q)\\ \implies pq&=p^2-2bp+p\\ \implies q&=p-2b+1\\ \implies b&=\tfrac{p-q+1}{2}. \end{align*}Substituting back into $p-q=b^2$, we solve $p-q=1$, done. $\square$
06.03.2024 02:46
$p=3, q=2$ is the answer. If $p,q$ are odd primes. Let $p-q=k^2, pq-q=m^2, p(q-1)=(m+k)(m-k)$. Since $p>q, p=m+k, q-1=m-k, p-q=2k-1$. Since $p,q$ are both odd, $p-q$ is even, which contradicts $p-q=2k+1$ which is odd. Thus, $q=2$. We have $p=(a+b)(a-b)$, which restricts $a-b=1$. Then, $b^2+2=p, 2b^2+2=b^2+2b+1, b=1\implies a=2, p=3$. Thus, $(3,2)$ is the only possible pair.
06.03.2024 02:54
suspicious $p-q=x^2$ and $pq-q=y^2$ $pq-p=p(q-1)=(y+x)(y-x)$ Notice $p>q$ and $p\mid x+y$. Notice $p>x,y$ so $p=x+y$. Then $q-1=y-x$. Then $p+q-1$ is even. Then $p+q$ is odd. So $q=2$. So $p-2=x^2$ and also $y=x+1$ so that $p=2x+1$. So $2x-1=x^2$. So $x^2-2x+1=0$. So $x=1$. So $p=3$. Answer $(3,2)$
16.03.2024 21:32
The only answer is $(3, 2)$, which works. Let $p - q = a^2$ and $pq - q = b^2$ for integers $a, b$. Evidently $p \ge q$. Since $$(b + a)(b - a) = pq - p = p(q - 1),$$we have either $p \mid b - a$ or $p \mid b + a$. But $b^2 = pq - q < p^2$ so $b < p$, and $p \mid b + a$. Since $a^2 = p - q < p^2$, we also have $a < p$, so $a + b < 2p$ and hence $a + b = p$. Then, we have $p = \sqrt{pq - q} + \sqrt{p - q}$, or $p - \sqrt{p - q} = \sqrt{pq - q}$, so \begin{align*} p^2 - 2p\sqrt{p - q} + p - q &= pq - q \\ \implies p^2 + p - pq &= 2p\sqrt{p - q} \\ \implies p - q - 2\sqrt{p - q} + 1 &= 0\\ \implies (\sqrt{p - q} - 1)^2 &= 0. \end{align*}Therefore $p - q = 1$, so we must have $p = 3$ and $q = 2$.
26.03.2024 14:20
$p-q=a^2$ and $pq-q=q^2b^2$, which means $p=qb^2+1$. So, $a^2-1=q(b^2-1)$. Case 1. $q=2$. Case 2. $q>2$. $pq-p=(qb-a)(qb+a)=p(q-1)$. Note that $p>qb$ so $p\mid qb+a$. But then $qb^2+1\leq qb+a$ so $qb(b-1)\leq a-1$. If $b=1$ then $a=1$ and $q=2$. Suppose $b>1$ then $(a^2-1)b/(b+1)\leq a-1$ which means $(a+1)b\leq b+1$ which is not possible. So we have a contradiction.
29.03.2024 23:05
Solution is $(p, q) = (3, 2)$. Let $p - q = m^2$ and $q(p-1) = n^2$. From this we get that $p(q-1) = (n+m)(n-m)$ and $p > q \implies p \mid m + n$ and since $n \mid p -1$ we get $n < p - 1$. Combining this with $n > m$ we get that $p = m + n$, so $q - 1 = n - m$. From this we get that $p + q = 2n + 1$ so $q = 2$(from $p > q$ and $p = q = 2$ not working). So then we have $p - 2 = m^2$ and $2(p-1) = n^2$. However since $n - m = q - 1 = 1$ we get $p = 2n - 1$. Plugging this in, we get that $2(2n-2) = n^2 \implies (n-2)^2 = 0 \implies n = 2$. So then $2(p-1) = 2^2 \implies p = 3$, done.
02.04.2024 00:04
19.05.2024 15:36
Let $(p,q)$ be a solution, suppose for the sake of contradiction that $p \geq q + 2$ Let $(a,b) \in \mathbb{N}^2$ such that $p - q = a^2$ and $pq - q = (bq)^2$ We have $pq - q = (bq)^2 \Rightarrow p = b^2q + 1$ A substitution yield $p - q = a^2 \Rightarrow b^2q + 1 - q = a^2 \Rightarrow q = \frac{a^2 - 1}{b^2 - 1}$ A substitution on the same equation yield $p - \frac{a^2 - 1}{b^2 - 1} = a^2 \Rightarrow p = \frac{(ab + 1)(ab - 1)}{b^2 - 1} \Rightarrow (b^2 - 1)p = (ab + 1)(ab - 1) $ Now our goal is to show that $a > b$ which is just equivalent to $p - q > \frac{p - 1}{q}$ or that $p(q - 1) > q^2 - 1$ hence finally $p > q + 1$ which is true since $p \geq q + 2 > q + 1$ Thus $ab + 1 > ab - 1 > b^2 - 1$ thus $b^2 - 1$ does not divide ab + 1 nor ab - 1. Hence their must exist two primes $p_1, p_2$ such that $p_1 \mid ab - 1$ and $p_2 \mid ab + 1$ but those two primes do not divide b^2 - 1, but since (b^2 - 1)p = (ab + 1)(ab - 1), those two primes must actually divide $p$ contradicting the fact that it's a prime. Hence we have $p \leq q + 1$, and $q \mid p - 1$ from $pq - q = (bq)^2$, we have that $p = q - 1$, since the two primes are consecutive, then $(p,q) = (3,2)$ is the only possible solution. Since $3 \times 2 - 2 = 4 = 2^2$ and $3 - 2 = 1 = 1^2$ then it is indeed a solution, and it is the only one.
23.08.2024 02:11
p-q=a^2 and pq-q=b^2 so b^2-a^2=(b+a)(b-a)=p(q-1) so p divides one of b+a or b-a.Observerve that p≠q so a^2 is a positive perfect square less than p and so a is less than p and b^2<p^2-p so b<p now we can apply a bounding.so p=a+b and thus b-a=q-1 so q-1+2a=p so q is even or q=2 now put q=2 in both equation p-2=a^2 and p-1=2c^2 now p is not of the form 3k±1 by both equation so p is 3.
26.08.2024 23:03
USAMO 2022 p4 We claim that $(3,2)$ is the only answer. Let $p-q=k^2$ and let $pq-q=l^2$, then we have that. \[p(q-1) = (k-l)(k+l) \]Hence we get that $p$ divide $k-l$ or $k+l$. By size reasons we get that $p=k+l$, this will force $q$ to be even and hence $q=2$, substituting this into the equation we get that $p$ must equal to $3$. Hence we are done.
22.11.2024 21:41
Let $p-q=n^2$ and $pq-q=m^2$ then $p(q-1)=(m+n)(m-n)$ and $q | p-1$ so we have that $2n=pa-b$ where $ab=q-1$ so $2n >p-q-1=n^2-1$ giving $n=1$ hence $(p,q)=(3,2)$.
22.11.2024 21:57
Fun little problem! Took a little while, but managed to get it just right
24.12.2024 19:11
This is so bad.
14.01.2025 05:20
Please contact westskigamer@gmail.com if there is an error with my solution for a $15 bounty by 3/18/2025.
Attachments:
