Difference between revisions of "2016 JBMO Problems/Problem 3"
(→Solution) |
Magnetoninja (talk | contribs) (→Solution) |
||
(7 intermediate revisions by one other user not shown) | |||
Line 10: | Line 10: | ||
It is given that <math>a,b,c \in \mathbb{Z} </math> | It is given that <math>a,b,c \in \mathbb{Z} </math> | ||
− | Let <math>(a-b) = -x</math> and <math>(b-c)=-y | + | Let <math>(a-b) = -x</math> and <math>(b-c)=-y</math> then <math>(c-a) = x+y</math> and <math> x,y \in \mathbb{Z}</math> |
+ | |||
+ | <math>(a-b)(b-c)(c-a) = xy(x+y)</math> | ||
We can then distinguish between two cases: | We can then distinguish between two cases: | ||
− | Case 1: If <math>n=0</math> | + | '''Case 1:''' If <math>n=0</math> |
+ | |||
+ | <math>2016^n = 2016^0 = 1 \equiv 1 (\mod 2016)</math> | ||
+ | |||
+ | <math>xy(x+y) = -2</math> | ||
+ | |||
+ | <math>-2 = (-1)(-1)(+2) = (-1)(+1)(+2)=(+1)(+1)(-2)</math> | ||
+ | |||
+ | <math>(x,y) \in \{(-1,-1), (-2,1), (-1,2)\}</math> | ||
+ | |||
+ | <math>(a,b,c) = (k, k+1, k+2)</math> and all cyclic permutations, with <math>k \in \mathbb{Z} </math> | ||
+ | |||
+ | '''Case 2:''' If <math>n>0</math> | ||
+ | |||
+ | <math>2016^n \equiv 0 (\mod 2016)</math> | ||
+ | |||
+ | <math>xy(x+y) + 4 = 2 \cdot 2016^n</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. | ||
+ | |||
+ | '''Method 1:''' Using modulo 9 | ||
+ | |||
+ | <math>xy(x+y) + 4 \equiv 0 (\mod 9)</math> | ||
+ | |||
+ | <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. | ||
+ | |||
+ | 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 \equiv 0 (\mod 3)</math> | ||
+ | |||
+ | <math>xy(x+y) \equiv 0 (\mod 3)</math> | ||
+ | |||
+ | <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>xy(x+y) \equiv 2 (\mod 9)</math> which is absurd since <math>xy(x+y) \equiv 5 (\mod 9)</math>. | ||
+ | |||
+ | '''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: | + | 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 |