Art of Problem Solving
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

2022 USAMO Problems/Problem 4

Revision as of 18:26, 31 March 2022 by Fclvbfm934 (talk | contribs) (Created page with "==Solution== 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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Solution

Since $q(p-1)$ is a perfect square and $q$ is prime, we should have $p - 1 = qb^2$ for some positive integer $b$. Let $a^2 = p - q$. Therefore, $q = p - a^2$, and substituting that into the $p - 1 = qb^2$ and solving for $p$ gives \[p = \frac{a^2b^2 - 1}{b^2 - 1} = \frac{(ab - 1)(ab + 1)}{b^2 - 1}.\] Notice that we also have \[p = \frac{a^2b^2 - 1}{b^2 - 1} = a^2 + \frac{a^2 - 1}{b^2 - 1}\] and so $b^2 - 1 | a^2 - 1$. We run through the cases

  • $a = 1$: Then $p - q = 1$ so $(p, q) = (3, 2)$, which works.
  • $a = b$: This means $p = a^2 + 1$, so $q = 1$, a contradiction.
  • $a > b$: This means that $b^2 - 1 < ab - 1$. Since $b^2 - 1$ can be split up into two factors $F_1, F_2$ such that $F_1 | ab - 1$ and $F_2 | ab + 1$, we get

\[p = \frac{ab - 1}{F_1} \cdot \frac{ab + 1}{F_2}\] and each factor is greater than $1$, contradicting the primality of $p$.

Thus, the only solution is $(p, q) = (3, 2)$.

Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=2022_USAMO_Problems/Problem_4&oldid=173116"