Difference between revisions of "2022 USAMO Problems/Problem 4"
m (→Problem) |
(→Solution 2) |
||
(2 intermediate revisions by 2 users not shown) | |||
Line 3: | Line 3: | ||
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== |
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 17: | 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) | ||
==See also== | ==See also== | ||
{{USAMO newbox|year=2022|num-b=3|num-a=5}} | {{USAMO newbox|year=2022|num-b=3|num-a=5}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 17:43, 10 April 2024
Contents
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)
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.