Difference between revisions of "2022 IMO Problems/Problem 5"
(→Solution 3) |
(→Solution 3) |
||
Line 82: | Line 82: | ||
− | ==Solution 3== | + | ==Solution 3(Unfinished)== |
− | 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. | + | 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. 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. |
− | + | ||
+ | Case 1: <math>b = k - 1</math> where <math>k</math> is a prime | ||
+ | |||
+ | 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>.(I have not finished proving why <math>a < k</math> will not have any solutions.) | ||
+ | |||
+ | Case 2: <math>b < a</math> | ||
+ | |||
+ | This just implies <math>a^{p} - p < a!</math>. Because of Wilson's Theorem, if <math>a = k - 1</math> where we use <math>k</math> again as a prime, then <math>a^{p} - p</math> will have a modular residue of anything but <math>-1 (\mod k)</math>.(I have not finished proving why <math>b < a</math> will also host no solutions). | ||
~ilikemath247365 | ~ilikemath247365 |
Revision as of 20:30, 18 June 2025
Problem
Find all triples of positive integers with
prime and
Video solution
https://www.youtube.com/watch?v=-AII0ldyDww [Video contains solutions to all day 2 problems]
Solution
Case 1:
- Since
is indivisible by
, then
must also be indivisible by
.
- If
, then
is divisible by
, so
must be a divisor of
, but
obviously has no solutions and we ruled out
already. For
, let's show that there are no solutions using simple inequalities.
- If
, then
and
by throwing away the remaining (non-negative) terms of binomial theorem. For any solution,
, which is impossible for
. That leaves us with
and
, but
for any integer
(proof by induction), so there are no solutions.
- If
, RHS is at most
and LHS is at least
(again from binomial theorem), which gives no solutions as well.
Case 2:
- Since
is divisible by
, then
must also be divisible by
.
- In addition, RHS is at most
, so
. We may write
, where
.
- Since
is a divisor of
and
it must also be a divisor of
, so
and
. We're looking for solutions of
.
- Let's factorise
: if
with
odd and
, it's
- Since
and
contain an odd number of odd terms (remember the assumption
aka
), they're odd. Also,
modulo
, so
and each following term is even but indivisible by
. The highest power of
dividing
is therefore
where
is the highest power dividing
.
- In comparison,
has factors
,
etc (up to
), and
other even factors, so it's divisible at least by
. Since
for
, the only possible solutions have
or
.
- If
, we reuse the inequalities
and
to show that there are no solutions for
.
- Finally,
isn't a factorial,
and
.
Case 3:
Just like in case 2, is divisible by
so
must also be divisible by
. However,
and
are also both divisible by
, so remainders modulo
tell us that no solutions exist.
Conclusion:
The only solutions are .
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)
WLOG, assume . Then,
must have a factor of
. Since
and
,
. But
is prime so
can only be
or the set of prime numbers. If
, then
which is impossible since
is a positive integer and so is
. Therefore,
must be the set of prime numbers specifically
. This means
. We can rearrange this to solve this Diophantine Equation:
with
being a prime number. Wilson's Theorem states that if
is a prime number, then
. This motivates us to consider different cases.
Case 1: where
is a prime
This means . Note that
is always even. Thus,
is odd. Let
. Here, we clearly see that
. Here, we only consider
. Note that
does indeed lead a solution of
so we have found our first solution triple.
Now, we go back to our original equation: ,
is a prime. Note that
. Consider
. Then,
. It is immediately obvious that
is the only solution which yields a solution of
. We will prove that is the second and last solution triple.
Case 1.1:
Then, . Since
is a prime, we have
. Note that if
, then this inequality will obviously not hold as all terms are strictly less than
. If
, then
. Using the same trick and dividing by
, we get a similar contradiction. Therefore, if
, we have no solution.
Case 1.2:
Note that will lead a contradiction in the modular arithmetic. Note that
. We have
. Notice
. It is immediately obvious that only
will hold solutions(If
, we can use a similar trick as above to prove that nothing will work). But note that
which means
. It is now obvious that
\implies
.(I have not finished proving why
will not have any solutions.)
Case 2:
This just implies . Because of Wilson's Theorem, if
where we use
again as a prime, then
will have a modular residue of anything but
.(I have not finished proving why
will also host no solutions).
~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 |