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 IMO Problems/Problem 5"

(added my own solution)
Line 47: Line 47:
  
 
- [[User:Xellos|Xellos]] ([[User talk:Xellos|talk]]) 13:31, 23 July 2022 (GMT+2)
 
- [[User:Xellos|Xellos]] ([[User talk:Xellos|talk]]) 13:31, 23 July 2022 (GMT+2)
 +
 +
==See Also==
 +
 +
{{IMO box|year=2022|num-b=4|num-a=6}}

Revision as of 00:55, 19 November 2023

Problem

Find all triples $(a,b,p)$ of positive integers with $p$ prime and \[a^p = b! + p\]

Video solution

https://www.youtube.com/watch?v=-AII0ldyDww [Video contains solutions to all day 2 problems]

Solution

Case 1: $b < p$

  • Since $b!$ is indivisible by $p$, then $a$ must also be indivisible by $p$.
  • If $a \le b$, then $a^p-b!$ is divisible by $a$, so $a$ must be a divisor of $p$, but $a=1$ obviously has no solutions and we ruled out $a=p$ already. For $a > b$, let's show that there are no solutions using simple inequalities.
  • If $b < a < p$, then $b! \le (a-1)! \le (a-1)^{a-1}$ and $a^p = (a-1+1)^p \ge (a-1)^p + p (a-1)^{p-1}$ by throwing away the remaining (non-negative) terms of binomial theorem. For any solution, $(a-1)^p + p (a-1)^{p-1} \le a^p = b!+p \le (a-1)^{a-1} + p$, which is impossible for $a-1 > 1$. That leaves us with $a=2$ and $b=1$, but $2^n > n+1$ for any integer $n \ge 2$ (proof by induction), so there are no solutions.
  • If $b < p < a$, RHS is at most $(p-1)^{p-1}+p$ and LHS is at least $(p+1)^p \ge p^p+p$ (again from binomial theorem), which gives no solutions as well.

Case 2: $p \le b < 2p$

  • Since $b!$ is divisible by $p$, then $a$ must also be divisible by $p$.
  • In addition, RHS is at most $(2p-1)!+p = p \prod_{i=1}^{p-1} (p-i)(p+i) + p < p^{2p-1} + p \le p^{2p}$, so $a < p^2$. We may write $a=pc$, where $1 \le c < p$.
  • Since $c$ is a divisor of $a^p$ and $b!$ it must also be a divisor of $p$, so $c=1$ and $a=p$. We're looking for solutions of $p^{p-1}-1 = b!/p$.
  • Let's factorise $p^{p-1}-1$: if $p-1 = 2^k \cdot n$ with $n$ odd and $k > 0$, it's

\[(p^n-1) \cdot (p^n+1) \cdot (p^{2n}+1) \cdot \ldots \cdot (p^{2^{k-1} n}+1) = (p-1) \cdot (1+p+\ldots+p^{n-1}) \cdot (p+1) \cdot (1-p+\ldots-p^{n-2}+p^{n-1}) \cdot (p^{2n}+1) \cdot \ldots \cdot (p^{2^{k-1} n}+1) \,.\]

  • Since $(1+p+\ldots+p^{n-1})$ and $(1-p+\ldots-p^{n-2}+p^{n-1})$ contain an odd number of odd terms (remember the assumption $k > 0$ aka $p \neq 2$), they're odd. Also, $p^2 \equiv 1$ modulo $4$, so $(p^{2n}+1)$ and each following term is even but indivisible by $4$. The highest power of $2$ dividing $p^{p-1}-1$ is therefore $2^{k + l + k-1}$ where $2^l$ is the highest power dividing $p+1$.
  • In comparison, $(p+1)!/p$ has factors $(p+1)$, $(2^k n)$ $(2^{k-1} n)$ etc (up to $2n$), and $(p-1)/2-k$ other even factors, so it's divisible at least by $2^{l+k(k+1)/2+(p-1)/2-k}$. Since $l+k(k+1)/2+(p-1)/2-k > l+2k-1$ for $p \ge 7$, the only possible solutions have $p < 7$ or $b = p$.
  • If $b=p$, we reuse the inequalities $p^{p-1} \ge (p-1)^{p-1}+p-1$ and $b!/p \le (p-1)^{p-1}$ to show that there are no solutions for $p > 2$.
  • Finally, $5^5-5 = 3120$ isn't a factorial, $3^3-3 = 24 = 4!$ and $2^2-2 = 2 = 2!$.

Case 3: $2p \le b$

Just like in case 2, $b!$ is divisible by $p$ so $a$ must also be divisible by $p$. However, $b!$ and $a^p$ are also both divisible by $p^2$, so remainders modulo $p^2$ tell us that no solutions exist.

Conclusion:

The only solutions are $(a,b,p) = (2,2,2), (3,4,3)$.

- Xellos (talk) 13:31, 23 July 2022 (GMT+2)

See Also

2022 IMO (Problems) • Resources
Preceded by
Problem 4 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 6
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2022_IMO_Problems/Problem_5&oldid=204602"