Difference between revisions of "2022 IMO Problems/Problem 5"

Latest revision as of 08:24, 6 September 2024

Problem

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

Video solution

https://youtu.be/d09PtqRSOuA

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)$ .

Solution 2

I considered the cases:

1) If $a$ is even, then it must:

  1.a) \(b \neq 1\) and \(p > 2\)
  1.b) \(b!\) is even and \(p = 2\)

2) If $a$ is odd, then it must:

  2.a) \(b \neq 1\) and \(p = 2\)
  2.b) \(b!\) is even and \(p > 2\)

Examining 1.a), we end up with an equation of the form $a^p = p+1$, which has no integer solutions.

In case 1.b), $b!$ can take values: 2, 6, 24, 120, 720, ..., so $b!+2$ takes values: 4, 8, 26, 122, 722, .... We observe that the only perfect square is 4 among the possible cases, as for $b \geq 5$, the result ends in 2, which is not a perfect square. Therefore, we have the triple $(2,2,2)$.

Case 2.a) yields $a^2 = 3$, which is rejected.

Examining the last case 2.b), we have for $b!$ the values: 2, 6, 24, 120, 720, 5040,

  i) \(b! = 2\), then \(a^p = 2+p\), which is rejected.
  ii) \(b! = 6\), then \(a^p = 6+p\), also does not give integer solutions.
  iii) \(b! = 24\), then \(a^p = 24+p\), giving a solution for \(p=3\). Thus, we have the triple \((3,4,3)\).
  iv) \(b \geq 5\):
     \(a^3 = b! + 3\), so \(a\) must end in 3 or 7, which does not give solutions.
     \(a^5 = b! + 5\), so \(a\) must end in 5, also not giving solutions.
     \(a^7 = b! + 7\), so \(a\) must end in 3, again not giving solutions.
     \(a^{11} = b! + 11\), no \(a \in \mathbb{Z^+}\) satisfies this.
     \(a^{19} = b! + 19\), similarly, no solutions.
     Other prime exponents reduce to these, as their last digit is one of \(\{1,3,7,9\}\)

The analysis of the last case is incomplete, which is why I wasn't initially sure about the number of triples. Therefore, with this approach (which is not strictly documented), we find the triples: $(2,2,2), (3,4,3)$.

@@ Line 4: / Line 4: @@
 ==Video solution==
+https://youtu.be/d09PtqRSOuA
 https://www.youtube.com/watch?v=-AII0ldyDww [Video contains solutions to all day 2 problems]
@@ Line 65: / Line 67: @@
 Case 2.a) yields \(a^2 = 3\), which is rejected.
-Examining the last case 2.b), we have for \(b!\) the values: 2, 6, 24, 120, 720, 5040, ...
+Examining the last case 2.b), we have for \(b!\) the values: 2, 6, 24, 120, 720, 5040,
     i) \(b! = 2\), then \(a^p = 2+p\), which is rejected.
     ii) \(b! = 6\), then \(a^p = 6+p\), also does not give integer solutions.
@@ Line 75: / Line 77: @@
        \(a^{11} = b! + 11\), no \(a \in \mathbb{Z^+}\) satisfies this.
        \(a^{19} = b! + 19\), similarly, no solutions.
-       Other prime exponents reduce to these, as their last digit is one of \(\{1,3,7,9\}\).
+       Other prime exponents reduce to these, as their last digit is one of \(\{1,3,7,9\}\)
 The analysis of the last case is incomplete, which is why I wasn't initially sure about the number of triples. Therefore, with this approach (which is not strictly documented), we find the triples: \((2,2,2), (3,4,3)\).

2022 IMO (Problems) • Resources
Preceded by Problem 4	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 6
All IMO Problems and Solutions

Page

Toolbox

Search