2022 IMO Problems/Problem 5

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

Solution 3

WLOG, assume $b \geq a$ . Then, $b!$ must have a factor of $a$ . Since $a\mid a^{p}$ and $a\mid b!$ , $a\mid p$ . But $p$ is prime so $a$ can only be $1$ or the set of prime numbers. If $a = 1$ , then $b! + p = 1$ which is impossible since $b$ is a positive integer and so is $p$ . Therefore, $a$ must be the set of prime numbers specifically $a = p$ . This means $a^{a} = b! + a$ . We can rearrange this to solve this Diophantine Equation: $a^{a} - a = b!$ with $a$ being a prime number. We automatically see a trivial case and that is when $a = 2$ . This yields a solution of $b = 2$ so we have found our first solution triple: $(a,b,p) = (2,2,2)$ . We now try the next smallest prime number and that is $3$ . So if $a = 3$ , then we have $24 = b!$ . Sure enough, this leads to a solution of $b = 4$ . So we have found our next(and last which we will prove) solution triple: $(a,b,p) = (3,4,3)$ . We now look at this same equation in a different manner: $a^{a} = a + b!$ . $a^{a}$ is just a list of several $a$ 's being multiplied together $a$ times. $b!$ is actually a product of decreasing consecutive numbers starting from $b$ . We have assumed $b \geq a$ . If $b = a$ , then it is obvious that the LHS outruns the RHS for any number starting from $a = 4$ . This is pretty obvious. $4^{4} = 256$ and the closest factorial to that is $5! = 120$ . We see that the RHS will never catch up. Even if $b > a$ , we would still see a similar case. Let's take $a = 5$ and $b = 6$ for example. $5^5 = 3125$ and $6! = 720$ . It is IMPOSSIBLE for the factorial function to catch up to the exponential function. Nevertheless, if you try higher values of $b$ , you'll still see that there aren't any solutions simply because the LHS is way faster than the RHS. You could perhaps prove this in many different ways: One way is to look at the different graphs of these functions. Moving on, assume now that $b < a$ . Now, $a^{p} > b^{p}$ . From here, we can establish that $b! > b^{p} - p$ . Rearranging, we see that $p > b^{p} - b!$ . Now from here, it should be pretty obvious that no solutions should exist. We have already stated that the exponential function grows much faster than the factorial function and therefore the difference would be much larger no matter what prime $p$ is. You can also test basic values out and see no solution should exist. Therefore, we should be comfortable with our two answers: $(2,2,2), (3,4,3)$ .

~ilikemath247365

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