Difference between revisions of "2022 USAMO Problems/Problem 4"
Fclvbfm934 (talk | contribs) (→Solution) |
(→Solution 3) |
||
(8 intermediate revisions by 6 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | ==Solution== | + | 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 1== | ||
Since <math>q(p-1)</math> is a perfect square and <math>q</math> is prime, we should have <math>p - 1 = qb^2</math> for some positive integer <math>b</math>. Let <math>a^2 = p - q</math>. Therefore, <math>q = p - a^2</math>, and substituting that into the <math>p - 1 = qb^2</math> and solving for <math>p</math> gives | Since <math>q(p-1)</math> is a perfect square and <math>q</math> is prime, we should have <math>p - 1 = qb^2</math> for some positive integer <math>b</math>. Let <math>a^2 = p - q</math>. Therefore, <math>q = p - a^2</math>, and substituting that into the <math>p - 1 = qb^2</math> and solving for <math>p</math> gives | ||
Line 15: | Line 17: | ||
Thus, the only solution is <math>(p, q) = (3, 2)</math>. | Thus, the only solution is <math>(p, q) = (3, 2)</math>. | ||
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | 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) | ||
+ | |||
+ | ==Solution 3== | ||
+ | |||
+ | We claim that the only solution is <math>(p,q) = (3,2)</math>. First, this clearly works, since <math>3-2=1^2</math> and <math>3\cdot2-2=2^2</math>. | ||
+ | |||
+ | Start as in Solution 2 - assign positive integers <math>m, n,</math> such that <math>p-q=m^2</math> and <math>pq-q=n^2.</math> Then, <math>pq-p=n^2-m^2,</math> or <math>p(q-1)=(n-m)(n+m).</math> | ||
+ | |||
+ | First, <math>p=q</math> is impossible, since <math>p^2-p = p(p-1)</math> is not a perfect square. Now notice that <math>m<p</math> and <math>n<\max(p,q-1).</math> But <math>p-q>0,</math> so <math>p\geq q-1.</math> Now, <math>m, n < p.</math> | ||
+ | |||
+ | Therefore, <math>n-m</math> can't ever be a factor of <math>p,</math> and <math>n+m<2p,</math> so <math>n+m=p.</math> Then, <math>n-m=q-1,</math> so <math>p-q=2m-1.</math> But <math>p-q=m^2,</math> so <math>m^2=2m-1,</math> or <math>m=1.</math> Therefore, one of <math>p</math> and <math>q</math> must be <math>2</math> (and <math>1</math> is not a prime). | ||
+ | |||
+ | Thus, we conclude that our claim is true. | ||
+ | |||
+ | (grape1984) | ||
==See also== | ==See also== | ||
− | {{USAMO newbox|year=2022|num-b= | + | {{USAMO newbox|year=2022|num-b=3|num-a=5}} |
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 22:58, 19 July 2025
Problem
Find all pairs of primes for which
and
are both perfect squares.
Solution 1
Since is a perfect square and
is prime, we should have
for some positive integer
. Let
. Therefore,
, and substituting that into the
and solving for
gives
Notice that we also have
and so
. We run through the cases
: Then
so
, which works.
: This means
, so
, a contradiction.
: This means that
. Since
can be split up into two factors
such that
and
, we get
and each factor is greater than
, contradicting the primality of
.
Thus, the only solution is .
Solution 2
Let ,
, where
are positive integers.
. So,
For
,
. Then
and
.
and
. Thus,
and we find
. Hence
.
For
, (
integer), by
,
. Let's examine in
,
. But we know that
. This is a contradiction and no solution for
.
For
, (
integer), by
,
. Let
, where
and
are integers. Since
, we see
. Thus, by
,
.
and
are same parity and
is even integer. So,
and
are both even integers. Therefore,
or
Therefore,
or
. For each case,
. But
, this gives a contradiction. No solution for
.
We conclude that the only solution is .
(Lokman GÖKÇE)
Solution 3
We claim that the only solution is . First, this clearly works, since
and
.
Start as in Solution 2 - assign positive integers such that
and
Then,
or
First, is impossible, since
is not a perfect square. Now notice that
and
But
so
Now,
Therefore, can't ever be a factor of
and
so
Then,
so
But
so
or
Therefore, one of
and
must be
(and
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.