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"

(→‎Solution 3(Unfinished))
(→‎Solution 3(Unfinished))
Line 97: Line 97:
 
Case 1.2: <math>a < k</math>
 
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>.(I have not finished proving why this doesn't work.)
+
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 </math>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 <math>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 </math>(\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
+
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.)
+
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>
+
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.  
+
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>
+
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)
+
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>
+
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.  
+
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.  
+
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>
+
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.
+
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.
  
−
Putting all the cases together, the two solutions are <math>\boxed{(a,b,p) = (2,2,2),(3,4,3)}</math>.   
+
Putting all the cases together, the two solutions are </math>\boxed{(a,b,p) = (2,2,2),(3,4,3)}$.   
  
 
~ilikemath247365
 
~ilikemath247365

Revision as of 12:21, 19 June 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:$ (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

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=251585"