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(Unfinished)

Consider $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. Wilson's Theorem states that if $p$ is a prime number, then $(p - 1)! \equiv -1(\mod p)$ . This motivates us to consider different cases.

Case 1: $b = k - 1$ where $k$ is a prime

This means $a^{a} - a \equiv -1(\mod k) = kq - 1 \implies a\mid kq - 1 \implies kq \equiv 1(\mod a) = ta + 1$ . Note that $a^{a} - a$ is always even. Thus, $kq$ is odd. Let $kq = 2c + 1$ . Here, we clearly see that $2c = ta$ . Here, we only consider $a = 2, c = t$ . Note that $a = 2$ does indeed lead a solution of $(a, b, p) = (2, 2, 2)$ so we have found our first solution triple.

Now, we go back to our original equation: $a^{a} - a = b!, b = k - 1$ , $k$ is a prime. Note that $k \geq 5$ . Consider $k = 5$ . Then, $a^{a} - a = 24 \implies a\mid 24$ . It is immediately obvious that $a = 3$ is the only solution which yields a solution of $(a, b, p) = (3, 4, 3)$ . We will prove that is the second and last solution triple.

Case 1.1: $a > k$

Then, $a^{a} - a > k^{k} - k \implies kq - 1 > k^{k} - k \implies kq + k - 1 > k^{k}$ . Since $k$ is a prime, we have $q + 1 - \frac{1}{k} > k^{k - 1}$ . Note that if $q < k$ , then this inequality will obviously not hold as all terms are strictly less than $k$ . If $q \geq k$ , then $k^{2} + k - 1 > k^{k}$ . Using the same trick and dividing by $k^{2}$ , we get a similar contradiction. Therefore, if $a > k$ , we have no solution.

Case 1.2: $a < k$

Note that $a = k$ will lead a contradiction in the modular arithmetic. Note that $k \geq 7$ . We have $a^{a} - a \leq 7q - 1$ . Notice $a^{a} - a < k^{k} - k$ . It is immediately obvious that only $7q - 1 \leq k^{k} - k$ will hold solutions(If $7q - 1 > k^{k} - k$ , we can use a similar trick as above to prove that nothing will work). But note that $k^{k} - k \geq 7^{7} - 7$ which means $7q - 1 \leq 7^{7} - 7$ . It is now obvious that $q \leq 7^{6} - \frac{6}{7}$ \implies $q \leq 7^{5}$ . Recall that $b \geq a$ . Thus, $k - 1 \geq a$ . We now have $k - 1 \mid a(a^{a - 1} - 1) \implies$ k - 1 \mid a $or$ k - 1 \mid a^{a - 1} - 1 $. Notice this just comes from$ a^{a} - a = (k - 1)! $as$ b = k - 1 $. But if$ k - 1 \mid a $, and because$ a \leq k - 1 $, it must be that$ a = k - 1 = b $. Therefore, we have$ a^{a} - a = a! $which already tells us that$ a = 2 $is the only solution, but we have already found this solution. Next, we move on to the case where$ a^{a - 1} - 1 \equiv 0(\mod k - 1) $. One thing we found was that$ q \leq 7^{5} $which came from$ k \geq 7 $. We will use this later. First, we consider if$ a - 1 $is prime. If it is, we can apply Fermat's Little Theorem to get$ a^{a - 1} \equiv a(\mod a - 1) \implies $a^{a - 1} - 1 \equiv 0(\mod a - 1)$ . But this tells us that if $k - 1 \mid a^{a - 1} - 1$ , then $a - 1 \mid a^{a - 1} - 1$ considering if $a - 1$ is prime. Note that if $a = k$ , this is impossible because Case 1.2 specifically considers $a < k$ . Therefore, we have that $b$ is actually bigger than at least one prime and we know one of them is $a - 1$ . Recall $b! = kq - 1$ . We have $(k - 1)! = kq - 1$ . We also have $(a - 1)! < kq - 1$ . Recall that if this was true, $a \mid kq - 1$ . Therefore, we can write $kq - 1 = az$ . Thus, $(a - 1)! < az$ . Because $k \geq 7$ , this tells us that $az \geq 7q - 1$ . Now, we recall that $(a - 1)! < 7q - 1 \implies$ (\frac{7q - 1}{z} - 1)! < 7q - 1 $. We note that$ (\frac{7q - 1}{z} - 1)! < 7q $. Note that$ q \leq 7^{5} $. We are assuming that if there exists a solution to Case 1.2, there should exist a solution to this new inequality and thus, there should exist a solution to when$ q = 7^{5} $. We see that$ (\frac{7^{6} - 1}{z} - 1)! < 7^{6} $. Note that$ z \leq 7 $because it divides$ k $and we are considering if equality holds, then$ k = 7 $. But this is obviously not true! Therefore, if$ a - 1 $is prime and$ a < k $, there exists no solutions. Now, we go to$ a - 1 $is composite. Recall that$ k $itself is a prime.$ a - 1 < k - 1$. (I have not finished proving this case.)

Case 1.3:$ (Error compiling LaTeX. Unknown error_msg)b $is anything but$ k - 1 $where$ k$is a prime

Recall that we have$ (Error compiling LaTeX. Unknown error_msg)a^{a} - a = b! $. Notice that$ b = k $will lead to a contradiction because$ a \geq 3 \implies a^{a} - a $is composite. Therefore,$ b = k + \alpha $where$ \alpha $is a constant of anything but$ -1, 0 $. Let$ r $be a prime that divides$ (k + \alpha)! $. Thus,$ r \mid a^{a} - a = a(a^{a - 1} - 1) $. Therefore, we know that$ r \mid k + \alpha - i $for$ 0 \leq i \leq k + \alpha - 1 $. We also know that$ r \mid a $or$ r \mid a^{a - 1} - 1 $. If we consider$ r \mid a $, because$ r $is a prime,$ r = a \implies a $is a prime number. In other words, we have just proven that if there exists a prime$ r $that divides$ b! $where$ b = k + \alpha $, then there also may exist a prime$ a $that also divides$ b! $. But because$ b \geq a $,$ a = b, b - 1, ..., 1 $. Therefore, at least one of$ b - j $where$ 0 \leq j \leq b - 1 $, must be a prime number. Now, we have$ a^{a} - a \leq b^{b} - b $. Let us consider the highest power of prime$ a $in$ b! $. We need to find$ v_a(b!) $. By Legendre's Formula, <cmath>e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor =\frac{n-S_{p}(n)}{p-1}</cmath>. We just need to find that$ \sum_{i=1}^{\infty} \left\lfloor \dfrac{b}{a^i}\right\rfloor = a $. If$ b $is a multiple of$ k $, this will not hold true simply be plugging in. Even if$ b = a + \beta $, because the sum is finite, it would imply$ \beta = 0 $which goes back to the case where$ b $is a multiple of$ a $. Therefore, the only condition for which this can hold is if$ a = 1 $which contradicts the part where$ 1 $must divide$ b - i $because$ 1 $is not prime. We now have to prove that this case doesn't hold even if$ r \mid a^{a - 1} - 1 $. In this case,$ a $is not necessarily prime. We can apply Fermat's Little Theorem if we assume$ a - 1 $is a prime. Then,$ a^{a - 1} \equiv a(\mod a - 1) $. This tells us that$ a^{a - 1} - 1 \equiv 0(\mod a - 1) $which tells us that$ a - 1 $is another prime that divides it. Therefore, there are two primes that divide$ a^{a - 1} - 1 $and those are$ r $and$ a - 1 $if$ a - 1 $is a prime. We conclude that either$ r = a - 1 $or$ a^{a - 1} - 1 $has more than one prime factor. If we consider$ r = a - 1 $, we can apply Legendre's again and see that it gives us the same result. If we have$ a^{a - 1} - 1 $has at least two distinct prime factors and two of them are$ r $and$ a - 1 $. This can only occur if$ a = 2 $(The other case will lead to a - 1 being composite which is not what we assumed). But we already considered this case. Therefore, we don't have a new solution here. Now, onto when$ a - 1$is not prime.(I have not finished proving this case.)

Case 2:$ (Error compiling LaTeX. Unknown error_msg)p < b < a $If we go back to the original equation of$ a^{p} = b! + p $, then we see$ p \mid b! + p $and thus$ p \mid a^{p} $. Therefore,$ a^{p} \equiv 0(\mod p) $. Fermat's Little Theorem states that$ a^{p} \equiv a(\mod p) $where$ p$is a prime. We have that exact same case here and thus this cannot hold.

Case 3:$ (Error compiling LaTeX. Unknown error_msg)b < p $,$ b < a $If$ b = p $, the same story as Case 2 would apply so we can discard that case. Let's consider a stronger inequality:$ b < p < a $or$ b < a < p$(Note: If a = p, we would get our original two triples so we can discard this case)

Case 3.1:$ (Error compiling LaTeX. Unknown error_msg)b < p < a $This shows that$ a^{a} > a! + a $. We will show this holds for all integers$ a \geq 3 $. This is our base case. We will prove this by induction. We want to show that if$ a^{a} > a! + a $holds true for all integers$ a \geq 3 $, then it must hold for all integers such that$ (a + 1)^{a + 1} > (a + 1)! + (a + 1) $. We have$ (a + 1)^{a + 1} = (a + 1)^{a} \cdot (a + 1) > a^{a} \cdot (a + 1) $. By our inductive statement,$ a^{a} \cdot (a + 1) > (a! + a)(a + 1) = (a + 1)! + a(a + 1) $. Thus, we wish to prove$ (a + 1)! + a(a + 1) > (a + 1)! + (a + 1) $. Remember, our base case was$ a \geq 3 $and thus for the inductive case,$ a + 1 \geq 3 $which means$ a \geq 2$which satisfies this inequality. Therefore, we have proved this case.

We have shown that if$ (Error compiling LaTeX. Unknown error_msg)b < p < a $, then$ a \geq 3 $. Then, it is obvious that$ b! + p \geq 3^{p} \implies b! \geq 3^{p} - p $. Since$ b < p \implies b! < p! \implies p! > 3^{p} - p $. We see that this only holds true for$ p \geq 7 $. But we have shown above that no prime above$ 7$will satisfy the original equation. Therefore, this inequality doesn't hold.

Case 3.2:$ (Error compiling LaTeX. Unknown error_msg)b < a < p $The same story applies as Case 3.1 but in this case$ p \geq 3 $. This will mean$ a^{3} = b! + 3, a^{5} = b! + 5 $and so on. We note that$ p \geq 7 $will not work based on our proof for Case 2. Thus, we just need to check$ a^{5} = b! + 5 $as the previous case led to a solution and unique solution of$ a = 3 $. Note that$ b^{5} < b! + 5 $. In fact, we will show this only holds when$ b = 0, 1 $. We will prove this by contradiction. Assume$ b^{5} < b! + 5 $for$ b \geq 2 $. We have$ b^{5} - 5 < b! \implies b^{5} - 5 < b(b - 1)(b - 2)...(2)(1) $. Dividing by$ b^{5} $gives$ 1 - \frac{5}{b^{5}} < \frac{b - 1}{b} \cdot \frac{b - 2}{b} \cdot \frac{b - 3}{b} \cdot \frac{b - 4}{b} \cdot (b - 5)(b - 6)...(2)(1) $. Note that we can write this as$ 1 - \frac{5}{b^{5}} < (1 - \frac{1}{b})(1 - \frac{2}{b})(1 - \frac{3}{b})(1 - \frac{4}{b})(b - 5)...(2)(1) $. If$ b \geq 5 $, the$ RHS $is tending towards$ 0 $by limits and the$ LHS $is tending towards$ 1 $by limits as$ b $approaches infinity. Therefore, we can check$ b = 2, 3, 4 $and see none of them hold. Thus our initial assumption was wrong and thus$ b^{5} < b! + 5 $only holds for$ b = 0,1 $and$ 0,1$aren't solutions to the original equation. Therefore, this final case doesn't have a solution either.

Putting all the cases together, the two solutions are$ (Error compiling LaTeX. Unknown error_msg)\boxed{(a,b,p) = (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