Difference between revisions of "2022 IMO Problems/Problem 5"
(Created page with "==Problem== Find all triples <math>(a,b,p)</math> of positive integers with <math>p</math> prime and <cmath>a^p = b! + p</cmath> ==Solution== https://www.youtube.com/watch?v=...") |
(added my own solution) |
||
Line 2: | Line 2: | ||
Find all triples <math>(a,b,p)</math> of positive integers with <math>p</math> prime and | Find all triples <math>(a,b,p)</math> of positive integers with <math>p</math> prime and | ||
<cmath>a^p = b! + p</cmath> | <cmath>a^p = b! + p</cmath> | ||
+ | |||
+ | ==Video solution== | ||
+ | https://www.youtube.com/watch?v=-AII0ldyDww [Video contains solutions to all day 2 problems] | ||
==Solution== | ==Solution== | ||
− | + | ||
+ | '''Case 1:''' <math>b < p</math> | ||
+ | |||
+ | * Since <math>b!</math> is indivisible by <math>p</math>, then <math>a</math> must also be indivisible by <math>p</math>. | ||
+ | |||
+ | * If <math>a \le b</math>, then <math>a^p-b!</math> is divisible by <math>a</math>, so <math>a</math> must be a divisor of <math>p</math>, but <math>a=1</math> obviously has no solutions and we ruled out <math>a=p</math> already. For <math>a > b</math>, let's show that there are no solutions using simple inequalities. | ||
+ | |||
+ | * If <math>b < a < p</math>, then <math>b! \le (a-1)! \le (a-1)^{a-1}</math> and <math>a^p = (a-1+1)^p \ge (a-1)^p + p (a-1)^{p-1}</math> by throwing away the remaining (non-negative) terms of binomial theorem. For any solution, <math>(a-1)^p + p (a-1)^{p-1} \le a^p = b!+p \le (a-1)^{a-1} + p</math>, which is impossible for <math>a-1 > 1</math>. That leaves us with <math>a=2</math> and <math>b=1</math>, but <math>2^n > n+1</math> for any integer <math>n \ge 2</math> (proof by induction), so there are no solutions. | ||
+ | |||
+ | * If <math>b < p < a</math>, RHS is at most <math>(p-1)^{p-1}+p</math> and LHS is at least <math>(p+1)^p \ge p^p+p</math> (again from binomial theorem), which gives no solutions as well. | ||
+ | |||
+ | '''Case 2:''' <math>p \le b < 2p</math> | ||
+ | |||
+ | * Since <math>b!</math> is divisible by <math>p</math>, then <math>a</math> must also be divisible by <math>p</math>. | ||
+ | |||
+ | * In addition, RHS is at most <math>(2p-1)!+p = p \prod_{i=1}^{p-1} (p-i)(p+i) + p < p^{2p-1} + p \le p^{2p}</math>, so <math>a < p^2</math>. We may write <math>a=pc</math>, where <math>1 \le c < p</math>. | ||
+ | |||
+ | * Since <math>c</math> is a divisor of <math>a^p</math> and <math>b!</math> it must also be a divisor of <math>p</math>, so <math>c=1</math> and <math>a=p</math>. We're looking for solutions of <math>p^{p-1}-1 = b!/p</math>. | ||
+ | |||
+ | * Let's factorise <math>p^{p-1}-1</math>: if <math>p-1 = 2^k \cdot n</math> with <math>n</math> odd and <math>k > 0</math>, it's | ||
+ | |||
+ | <cmath>(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) \,.</cmath> | ||
+ | |||
+ | * Since <math>(1+p+\ldots+p^{n-1})</math> and <math>(1-p+\ldots-p^{n-2}+p^{n-1})</math> contain an odd number of odd terms (remember the assumption <math>k > 0</math> aka <math>p \neq 2</math>), they're odd. Also, <math>p^2 \equiv 1</math> modulo <math>4</math>, so <math>(p^{2n}+1)</math> and each following term is even but indivisible by <math>4</math>. The highest power of <math>2</math> dividing <math>p^{p-1}-1</math> is therefore <math>2^{k + l + k-1}</math> where <math>2^l</math> is the highest power dividing <math>p+1</math>. | ||
+ | |||
+ | * In comparison, <math>(p+1)!/p</math> has factors <math>(p+1)</math>, <math>(2^k n)</math> <math>(2^{k-1} n)</math> etc (up to <math>2n</math>), and <math>(p-1)/2-k</math> other even factors, so it's divisible at least by <math>2^{l+k(k+1)/2+(p-1)/2-k}</math>. Since <math>l+k(k+1)/2+(p-1)/2-k > l+2k-1</math> for <math>p \ge 7</math>, the only possible solutions have <math>p < 7</math> or <math>b = p</math>. | ||
+ | |||
+ | * If <math>b=p</math>, we reuse the inequalities <math>p^{p-1} \ge (p-1)^{p-1}+p-1</math> and <math>b!/p \le (p-1)^{p-1}</math> to show that there are no solutions for <math>p > 2</math>. | ||
+ | |||
+ | * Finally, <math>5^5-5 = 3120</math> isn't a factorial, <math>3^3-3 = 24 = 4!</math> and <math>2^2-2 = 2 = 2!</math>. | ||
+ | |||
+ | '''Case 3:''' <math>2p \le b</math> | ||
+ | |||
+ | Just like in case 2, <math>b!</math> is divisible by <math>p</math> so <math>a</math> must also be divisible by <math>p</math>. However, <math>b!</math> and <math>a^p</math> are also both divisible by <math>p^2</math>, so remainders modulo <math>p^2</math> tell us that no solutions exist. | ||
+ | |||
+ | '''Conclusion:''' | ||
+ | |||
+ | The only solutions are <math>(a,b,p) = (2,2,2), (3,4,3)</math>. | ||
+ | |||
+ | - [[User:Xellos|Xellos]] ([[User talk:Xellos|talk]]) 13:31, 23 July 2022 (GMT+2) |
Revision as of 07:38, 23 July 2022
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 .