Difference between revisions of "2016 JBMO Problems/Problem 3"
Magnetoninja (talk | contribs) (→Solution) |
|||
(5 intermediate revisions by one other user not shown) | |||
Line 29: | Line 29: | ||
'''Case 2:''' If <math>n>0</math> | '''Case 2:''' If <math>n>0</math> | ||
+ | |||
<math>2016^n \equiv 0 (\mod 2016)</math> | <math>2016^n \equiv 0 (\mod 2016)</math> | ||
<math>xy(x+y) + 4 = 2 \cdot 2016^n</math> | <math>xy(x+y) + 4 = 2 \cdot 2016^n</math> | ||
− | <math>2016 = 2^5 \cdot 3^2 \cdot 7</math> | + | <math>2016 = 2^5 \cdot 3^2 \cdot 7</math> is the unique prime factorization. |
Using module arithmetic, it can be proved that there is no solution. | Using module arithmetic, it can be proved that there is no solution. | ||
Line 39: | Line 40: | ||
'''Method 1:''' Using modulo 9 | '''Method 1:''' Using modulo 9 | ||
− | <math>xy(x+y) + 4 | + | <math>xy(x+y) + 4 \equiv 0 (\mod 9)</math> |
− | <math>xy(x+y) | + | <math>xy(x+y) \equiv 0 (\mod 9)</math> |
In general, it is impossible to find integer values for <math>x,y</math> to satisfy the last statement. | In general, it is impossible to find integer values for <math>x,y</math> to satisfy the last statement. | ||
− | One way to show this is by checking all 27 cases modulo 9. An other one is the following: | + | One way to show this is by checking all 27 possible cases modulo 9. An other one is the following: |
− | <math>xy(x+y) + 4 | + | <math>xy(x+y) + 4 \equiv 0 (\mod 3)</math> |
− | <math>xy(x+y) | + | <math>xy(x+y) \equiv 0 (\mod 3)</math> |
− | <math>x | + | <math>x \equiv 1 (\mod 3)</math> and <math>y \equiv 1 (\mod 3)</math> |
<math>x,y \in \{ 1(\mod 3), 4(\mod 3), 7(\mod 3) \}</math> | <math>x,y \in \{ 1(\mod 3), 4(\mod 3), 7(\mod 3) \}</math> | ||
Line 58: | Line 59: | ||
'''Method 2:''' Using modulo 7 | '''Method 2:''' Using modulo 7 | ||
+ | |||
+ | <math>xy(x+y) + 4 \equiv 0 (\mod 7)</math> | ||
+ | |||
+ | <math>xy(x+y) \equiv 3 (\mod 7)</math> | ||
+ | |||
+ | In general, it is impossible to find integer values for <math>x,y</math> to satisfy the last statement. | ||
+ | |||
+ | One way to show this is by checking all 15 possible cases modulo 7. | ||
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | First, we check when <math>n>0</math>. WLOG, let <math>a>b</math> since one of the factors of <math>(a-b)(b-c)(c-a)</math> must be positive. Then, <math>a>c>b</math> is forced. Let <math>a-c=d_1</math> and <math>c-b=d_2</math> so we want <math>2(2016^n-2)=4(1008^{2n-1}-1)=d_1d_2(d_1+d_2)</math>. Now, we have two cases, one of <math>d_1</math> or <math>d_2</math> is odd and the other is even, or they are both odd and <math>d_1+d_2\equiv 0\pmod{4}</math>. | ||
+ | Case 1: WLOG <math>d_1</math> is odd and <math>d_2</math> is even. | ||
+ | Then <math>d_2\equiv 0\pmod{4}</math>. Let <math>d_2=4s</math> where <math>s</math> is odd. Note that <math>s</math> cannot be even since the product cannot be divisible by 8. After dividing the modular equation by 4, we get <math>1008^o\equiv 1\pmod {(4s+d_1)(sd_1)}, o=2n-1</math>. | ||
+ | Remember that Fermat's LIttle Theorem states that <math>a^{p-1}\equiv 1\pmod{p}</math> if <math>p\nmid{a}</math>. There must be a prime <math>p</math> that divides <math>(4s+d_1)(sd_1)</math>, and by CRT, that means that <math>o</math> is one less than that <math>p</math>. However, <math>o</math> must be odd so the only <math>p</math> that works is <math>p=2</math>. Thus, this implies that <math>(4s+d_1)(sd_1)</math> has no divisor of any other prime other than 2, so it must be a power of 2. However, since <math>d_1</math> is odd, it cannot have a factor of 2. We arrive at a contradiction. | ||
+ | |||
+ | Case 2: <math>d_1, d_2\equiv 1\pmod{2}, d_1+d_2\equiv 0\pmod{4}</math> | ||
== See also == | == See also == |
Latest revision as of 15:14, 28 November 2023
Contents
Problem
Find all triplets of integers such that the number
is a power of .
(A power of is an integer of form
,where
is a non-negative integer.)
Solution
It is given that
Let and
then
and
We can then distinguish between two cases:
Case 1: If
and all cyclic permutations, with
Case 2: If
is the unique prime factorization.
Using module arithmetic, it can be proved that there is no solution.
Method 1: Using modulo 9
In general, it is impossible to find integer values for to satisfy the last statement.
One way to show this is by checking all 27 possible cases modulo 9. An other one is the following:
and
which is absurd since
.
Method 2: Using modulo 7
In general, it is impossible to find integer values for to satisfy the last statement.
One way to show this is by checking all 15 possible cases modulo 7.
Solution 2
First, we check when . WLOG, let
since one of the factors of
must be positive. Then,
is forced. Let
and
so we want
. Now, we have two cases, one of
or
is odd and the other is even, or they are both odd and
.
Case 1: WLOG
is odd and
is even.
Then
. Let
where
is odd. Note that
cannot be even since the product cannot be divisible by 8. After dividing the modular equation by 4, we get
.
Remember that Fermat's LIttle Theorem states that
if
. There must be a prime
that divides
, and by CRT, that means that
is one less than that
. However,
must be odd so the only
that works is
. Thus, this implies that
has no divisor of any other prime other than 2, so it must be a power of 2. However, since
is odd, it cannot have a factor of 2. We arrive at a contradiction.
Case 2:
See also
2016 JBMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 | ||
All JBMO Problems and Solutions |