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

Latest revision as of 13:49, 23 July 2025

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: $b$ is anything but $k - 1$ where $k$ is a prime

Recall that we have $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, $e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor =\frac{n-S_{p}(n)}{p-1}$ . 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: $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: $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: $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 $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: $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.

Hence, the two solutions are $\boxed{(a,b,p) = (2,2,2),(3,4,3)}$ .

~ilikemath247365

@@ Line 81: / Line 81: @@
 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)==
-==Solution 3==
+Consider <math>b \geq a</math>. Then, <math>b!</math> must have a factor of <math>a</math>. Since <math>a\mid a^{p}</math> and <math>a\mid b!</math>, <math>a\mid p</math>. But <math>p</math> is prime so <math>a</math> can only be <math>1</math> or the set of prime numbers. If <math>a = 1</math>, then <math>b! + p = 1</math> which is impossible since <math>b</math> is a positive integer and so is <math>p</math>. Therefore, <math>a</math> must be the set of prime numbers specifically <math>a = p</math>. This means <math>a^{a} = b! + a</math>. We can rearrange this to solve this Diophantine Equation: <math>a^{a} - a = b!</math> with <math>a</math> being a prime number. Wilson's Theorem states that if <math>p</math> is a prime number, then <math>(p - 1)! \equiv -1(\mod p)</math>. This motivates us to consider different cases.
-WLOG, assume <math>b \geq a</math>. Then, <math>b!</math> must have a factor of <math>a</math>. Since <math>a\mid a^{p}</math> and <math>a\mid b!</math>, <math>a\mid p</math>. But <math>p</math> is prime so <math>a</math> can only be <math>1</math> or the set of prime numbers. If <math>a = 1</math>, then <math>b! + p = 1</math> which is impossible since <math>b</math> is a positive integer and so is <math>p</math>. Therefore, <math>a</math> must be the set of prime numbers specifically <math>a = p</math>. This means <math>a^{a} = b! + a</math>. We can rearrange this to solve this Diophantine Equation: <math>a^{a} - a = b!</math> with <math>a</math> being a prime number. We automatically see a trivial case and that is when <math>a = 2</math>. This yields a solution of <math>b = 2</math> so we have found our first solution triple: <math>(a,b,p) = (2,2,2)</math>. We now try the next smallest prime number and that is <math>3</math>. So if <math>a = 3</math>, then we have <math>24 = b!</math>. Sure enough, this leads to a solution of <math>b = 4</math>. So we have found our next(and last which we will prove) solution triple: <math>(a,b,p) = (3,4,3)</math>. We now look at this same equation in a different manner: <math>a^{a} = a + b!</math>. <math>a^{a}</math> is just a list of several <math>a</math>'s being multiplied together <math>a</math> times. <math>b!</math> is actually a product of decreasing consecutive numbers starting from <math>b</math>. We have assumed <math>b \geq a</math>. If <math>b = a</math>, then it is obvious that the LHS outruns the RHS for any number starting from <math>a = 4</math>. This is pretty obvious. <math>4^{4} = 256</math> and the closest factorial to that is <math>5! = 120</math>. We see that the RHS will never catch up. Even if <math>b > a</math>, we would still see a similar case. Let's take <math>a = 5</math> and <math>b = 6</math> for example. <math>5^5 = 3125</math> and <math>6! = 720</math>. It is IMPOSSIBLE for the factorial function to catch up to the exponential function. Nevertheless, if you try higher values of <math>b</math>, 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.
+Case 1: <math>b = k - 1</math> where <math>k</math> is a prime
-Moving on, assume now that <math>b < a</math>. Now, <math>a^{p} > b^{p}</math>. From here, we can establish that <math>b! > b^{p} - p</math>. Rearranging, we see that <math>p > b^{p} - b!</math>. 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 <math>p</math> is. You can also test basic values out and see no solution should exist. Therefore, we should be comfortable with our two answers: <math>(2,2,2), (3,4,3)</math>.
+This means <math>a^{a} - a \equiv -1(\mod k) = kq - 1 \implies a\mid kq - 1 \implies kq \equiv 1(\mod a) = ta + 1</math>. Note that <math>a^{a} - a</math> is always even. Thus, <math>kq</math> is odd. Let <math>kq = 2c + 1</math>. Here, we clearly see that <math>2c = ta</math>. Here, we only consider <math>a = 2, c = t</math>. Note that <math>a = 2</math> does indeed lead a solution of <math>(a, b, p) = (2, 2, 2)</math> so we have found our first solution triple.
+Now, we go back to our original equation: <math>a^{a} - a = b!, b = k - 1</math>, <math>k</math> is a prime. Note that <math>k \geq 5</math>. Consider <math>k = 5</math>. Then, <math>a^{a} - a = 24 \implies a\mid 24</math>. It is immediately obvious that <math>a = 3</math> is the only solution which yields a solution of <math>(a, b, p) = (3, 4, 3)</math>. We will prove that is the second and last solution triple.
+Case 1.1: <math>a > k</math>
+Then, <math>a^{a} - a > k^{k} - k \implies kq - 1 > k^{k} - k \implies kq + k - 1 > k^{k}</math>. Since <math>k</math> is a prime, we have <math>q + 1 - \frac{1}{k} > k^{k - 1}</math>. Note that if <math>q < k</math>, then this inequality will obviously not hold as all terms are strictly less than <math>k</math>. If <math>q \geq k</math>, then <math>k^{2} + k - 1 > k^{k}</math>. Using the same trick and dividing by <math>k^{2}</math>, we get a similar contradiction. Therefore, if <math>a > k</math>, we have no solution.
+Case 1.2: <math>a < k</math>
+Note that <math>a = k</math> will lead a contradiction in the modular arithmetic. Note that <math>k \geq 7</math>. We have <math>a^{a} - a \leq 7q - 1</math>. Notice <math>a^{a} - a < k^{k} - k</math>. It is immediately obvious that only <math>7q - 1 \leq k^{k} - k</math> will hold solutions(If <math>7q - 1 > k^{k} - k</math>, we can use a similar trick as above to prove that nothing will work). But note that <math>k^{k} - k \geq 7^{7} - 7</math> which means <math>7q - 1 \leq 7^{7} - 7</math>. It is now obvious that <math>q \leq 7^{6} - \frac{6}{7}</math> \implies <math>q \leq 7^{5}</math>. Recall that <math>b \geq a</math>. Thus, <math>k - 1 \geq a</math>. We now have <math>k - 1 \mid a(a^{a - 1} - 1) \implies k - 1 \mid a</math> or <math>k - 1 \mid a^{a - 1} - 1</math>. Notice this just comes from <math>a^{a} - a = (k - 1)!</math> as <math>b = k - 1</math>. But if <math>k - 1 \mid a</math>, and because <math>a \leq k - 1</math>, it must be that <math>a = k - 1 = b</math>. Therefore, we have <math>a^{a} - a = a!</math> which already tells us that <math>a = 2</math> is the only solution, but we have already found this solution. Next, we move on to the case where <math>a^{a - 1} - 1 \equiv 0(\mod k - 1)</math>. One thing we found was that <math>q \leq 7^{5}</math> which came from <math>k \geq 7</math>. We will use this later. First, we consider if <math>a - 1</math> is prime. If it is, we can apply Fermat's Little Theorem to get <math>a^{a - 1} \equiv a(\mod a - 1) \implies a^{a - 1} - 1 \equiv 0(\mod a - 1)</math>. But this tells us that if <math>k - 1 \mid a^{a - 1} - 1</math>, then <math>a - 1 \mid a^{a - 1} - 1</math> considering if <math>a - 1</math> is prime. Note that if <math>a = k</math>, this is impossible because Case 1.2 specifically considers <math>a < k</math>. Therefore, we have that <math>b</math> is actually bigger than at least one prime and we know one of them is <math>a - 1</math>. Recall <math>b! = kq - 1</math>. We have <math>(k - 1)! = kq - 1</math>. We also have <math>(a - 1)! < kq - 1</math>. Recall that if this was true, <math>a \mid kq - 1</math>. Therefore, we can write <math>kq - 1 = az</math>. Thus, <math>(a - 1)! < az</math>. Because <math>k \geq 7</math>, this tells us that <math>az \geq 7q - 1</math>. Now, we recall that <math>(a - 1)! < 7q - 1 \implies (\frac{7q - 1}{z} - 1)! < 7q - 1</math>. We note that <math>(\frac{7q - 1}{z} - 1)! < 7q</math>. Note that <math>q \leq 7^{5}</math>. 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 <math>q = 7^{5}</math>. We see that <math>(\frac{7^{6} - 1}{z} - 1)! < 7^{6}</math>. Note that <math>z \leq 7</math> because it divides <math>k</math> and we are considering if equality holds, then <math>k = 7</math>. But this is obviously not true! Therefore, if <math>a - 1</math> is prime and <math>a < k</math>, there exists no solutions. Now, we go to <math>a - 1</math> is composite. Recall that <math>k</math> itself is a prime. <math>a - 1 < k - 1</math>. (I have not finished proving this case.)
+Case 1.3: <math>b</math> is anything but <math>k - 1</math> where <math>k</math> is a prime
+Recall that we have <math>a^{a} - a = b!</math>. Notice that <math>b = k</math> will lead to a contradiction because <math>a \geq 3 \implies a^{a} - a</math> is composite. Therefore, <math>b = k + \alpha</math> where <math>\alpha</math> is a constant of anything but <math>-1, 0</math>. Let <math>r</math> be a prime that divides <math>(k + \alpha)!</math>. Thus, <math>r \mid a^{a} - a = a(a^{a - 1} - 1)</math>. Therefore, we know that <math>r \mid k + \alpha - i</math> for <math>0 \leq i \leq k + \alpha - 1</math>. We also know that <math>r \mid a</math> or <math>r \mid a^{a - 1} - 1</math>. If we consider <math>r \mid a</math>, because <math>r</math> is a prime, <math>r = a \implies a</math> is a prime number. In other words, we have just proven that if there exists a prime <math>r</math> that divides <math>b!</math> where <math>b = k + \alpha</math>, then there also may exist a prime <math>a</math> that also divides <math>b!</math>. But because <math>b \geq a</math>, <math>a = b, b - 1, ..., 1</math>. Therefore, at least one of <math>b - j</math> where <math>0 \leq j \leq b - 1</math>, must be a prime number. Now, we have <math>a^{a} - a \leq b^{b} - b</math>. Let us consider the highest power of prime <math>a</math> in <math>b!</math>. We need to find <math>v_a(b!)</math>. 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 <math>\sum_{i=1}^{\infty} \left\lfloor \dfrac{b}{a^i}\right\rfloor = a</math>. If <math>b</math> is a multiple of <math>k</math>, this will not hold true simply be plugging in. Even if <math>b = a + \beta</math>, because the sum is finite, it would imply <math>\beta = 0</math> which goes back to the case where <math>b</math> is a multiple of <math>a</math>. Therefore, the only condition for which this can hold is if <math>a = 1</math> which contradicts the part where <math>1</math> must divide <math>b - i</math> because <math>1</math> is not prime. We now have to prove that this case doesn't hold even if <math>r \mid a^{a - 1} - 1</math>. In this case, <math>a</math> is not necessarily prime. We can apply Fermat's Little Theorem if we assume <math>a - 1</math> is a prime. Then, <math>a^{a - 1} \equiv a(\mod a - 1)</math>. This tells us that <math>a^{a - 1} - 1 \equiv 0(\mod a - 1)</math> which tells us that <math>a - 1</math> is another prime that divides it. Therefore, there are two primes that divide <math>a^{a - 1} - 1</math> and those are <math>r</math> and <math>a - 1</math> if <math>a - 1</math> is a prime. We conclude that either <math>r = a - 1</math> or <math>a^{a - 1} - 1</math> has more than one prime factor. If we consider <math>r = a - 1</math>, we can apply Legendre's again and see that it gives us the same result. If we have <math>a^{a - 1} - 1</math> has at least two distinct prime factors and two of them are <math>r</math> and <math>a - 1</math>. This can only occur if <math>a = 2</math>(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 <math>a - 1</math> is not prime.(I have not finished proving this case.)
+Case 2: <math>p < b < a</math>
+If we go back to the original equation of <math>a^{p} = b! + p</math>, then we see <math>p \mid b! + p</math> and thus <math>p \mid a^{p}</math>. Therefore, <math>a^{p} \equiv 0(\mod p)</math>. Fermat's Little Theorem states that <math>a^{p} \equiv a(\mod p)</math> where <math>p</math> is a prime. We have that exact same case here and thus this cannot hold.
+Case 3: <math>b < p</math>, <math>b < a</math>
+If <math>b = p</math>, the same story as Case 2 would apply so we can discard that case. Let's consider a stronger inequality: <math>b < p < a</math> or <math>b < a < p</math> (Note: If a = p, we would get our original two triples so we can discard this case)
+Case 3.1: <math>b < p < a</math>
+This shows that <math>a^{a} > a! + a</math>. We will show this holds for all integers <math>a \geq 3</math>. This is our base case. We will prove this by induction. We want to show that if <math>a^{a} > a! + a</math> holds true for all integers <math>a \geq 3</math>, then it must hold for all integers such that <math>(a + 1)^{a + 1} > (a + 1)! + (a + 1)</math>. We have <math>(a + 1)^{a + 1} = (a + 1)^{a} \cdot (a + 1) > a^{a} \cdot (a + 1)</math>. By our inductive statement, <math>a^{a} \cdot (a + 1) > (a! + a)(a + 1) = (a + 1)! + a(a + 1)</math>. Thus, we wish to prove <math>(a + 1)! + a(a + 1) > (a + 1)! + (a + 1)</math>. Remember, our base case was <math>a \geq 3</math> and thus for the inductive case, <math>a + 1 \geq 3</math> which means <math>a \geq 2</math> which satisfies this inequality. Therefore, we have proved this case.
+We have shown that if <math>b < p < a</math>, then <math>a \geq 3</math>. Then, it is obvious that <math>b! + p \geq 3^{p} \implies b! \geq 3^{p} - p</math>. Since <math>b < p \implies b! < p! \implies p! > 3^{p} - p</math>. We see that this only holds true for <math>p \geq 7</math>. But we have shown above that no prime above <math>7</math> will satisfy the original equation. Therefore, this inequality doesn't hold.
+Case 3.2: <math>b < a < p</math>
+The same story applies as Case 3.1 but in this case <math>p \geq 3</math>. This will mean <math>a^{3} = b! + 3, a^{5} = b! + 5</math> and so on. We note that <math>p \geq 7</math> will not work based on our proof for Case 2. Thus, we just need to check <math>a^{5} = b! + 5</math> as the previous case led to a solution and unique solution of <math>a = 3</math>. Note that <math>b^{5} < b! + 5</math>. In fact, we will show this only holds when <math>b = 0, 1</math>. We will prove this by contradiction. Assume <math>b^{5} < b! + 5</math> for <math>b \geq 2</math>. We have <math>b^{5} - 5 < b! \implies b^{5} - 5 < b(b - 1)(b - 2)...(2)(1)</math>. Dividing by <math>b^{5}</math> gives <math>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)</math>. Note that we can write this as <math>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)</math>. If <math>b \geq 5</math>, the <math>RHS</math> is tending towards <math>0</math> by limits and the <math>LHS</math> is tending towards <math>1</math> by limits as <math>b</math> approaches infinity. Therefore, we can check <math>b = 2, 3, 4</math> and see none of them hold. Thus our initial assumption was wrong and thus <math>b^{5} < b! + 5</math> only holds for <math>b = 0,1</math> and <math>0,1</math> aren't solutions to the original equation. Therefore, this final case doesn't have a solution either.
+Hence, the two solutions are <math>\boxed{(a,b,p) = (2,2,2),(3,4,3)}</math>.
 ~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