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 "2016 JBMO Problems/Problem 3"

(→‎Solution)
(→‎Solution)
 
(6 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> 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 37: Line 40:
 
'''Method 1:''' Using modulo 9
 
'''Method 1:''' Using modulo 9
  
−
<math>xy(x+y) + 4 = 0 \equiv (\mod 9)</math>
+
<math>xy(x+y) + 4 \equiv 0 (\mod 9)</math>
  
−
<math>xy(x+y) = 5 \equiv (\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.
 
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 = 0 \equiv (\mod 3)</math>
+
<math>xy(x+y) + 4 \equiv 0 (\mod 3)</math>
  
−
<math>xy(x+y) = 2 \equiv (\mod 3)</math>
+
<math>xy(x+y) \equiv 0 (\mod 3)</math>
  
−
<math>x = 1 \equiv (\mod 3)</math> and <math>y = 1 \equiv (\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>x,y \in \{ 1(\mod 3), 4(\mod 3), 7(\mod 3) \}</math>
Line 57: Line 60:
 
'''Method 2:''' Using modulo 7
 
'''Method 2:''' Using modulo 7
  
−
<math>2016 = 2^5 \cdot 3^2 \cdot 7</math>
+
<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 14:14, 28 November 2023

Problem

Find all triplets of integers $(a,b,c)$ such that the number 

\[N = \frac{(a-b)(b-c)(c-a)}{2} + 2\]

is a power of $2016$.

(A power of $2016$ is an integer of form $2016^n$,where $n$ is a non-negative integer.)

Solution

It is given that $a,b,c \in \mathbb{Z}$

Let $(a-b) = -x$ and $(b-c)=-y$ then $(c-a) = x+y$ and $x,y \in \mathbb{Z}$

$(a-b)(b-c)(c-a) = xy(x+y)$

We can then distinguish between two cases:

Case 1: If $n=0$

$2016^n = 2016^0 = 1 \equiv 1 (\mod 2016)$

$xy(x+y) = -2$

$-2 = (-1)(-1)(+2) = (-1)(+1)(+2)=(+1)(+1)(-2)$

$(x,y) \in \{(-1,-1), (-2,1), (-1,2)\}$

$(a,b,c) = (k, k+1, k+2)$ and all cyclic permutations, with $k \in \mathbb{Z}$

Case 2: If $n>0$

$2016^n \equiv 0 (\mod 2016)$

$xy(x+y) + 4 = 2 \cdot 2016^n$

$2016 = 2^5 \cdot 3^2 \cdot 7$ is the unique prime factorization.

Using module arithmetic, it can be proved that there is no solution.

Method 1: Using modulo 9

$xy(x+y) + 4 \equiv 0 (\mod 9)$

$xy(x+y) \equiv 0 (\mod 9)$

In general, it is impossible to find integer values for $x,y$ 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:

$xy(x+y) + 4 \equiv 0 (\mod 3)$

$xy(x+y) \equiv 0 (\mod 3)$

$x \equiv 1 (\mod 3)$ and $y \equiv 1 (\mod 3)$

$x,y \in \{ 1(\mod 3), 4(\mod 3), 7(\mod 3) \}$

$xy(x+y) \equiv 2 (\mod 9)$ which is absurd since $xy(x+y) \equiv 5 (\mod 9)$.

Method 2: Using modulo 7

$xy(x+y) + 4 \equiv 0 (\mod 7)$

$xy(x+y) \equiv 3 (\mod 7)$

In general, it is impossible to find integer values for $x,y$ 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 $n>0$. WLOG, let $a>b$ since one of the factors of $(a-b)(b-c)(c-a)$ must be positive. Then, $a>c>b$ is forced. Let $a-c=d_1$ and $c-b=d_2$ so we want $2(2016^n-2)=4(1008^{2n-1}-1)=d_1d_2(d_1+d_2)$. Now, we have two cases, one of $d_1$ or $d_2$ is odd and the other is even, or they are both odd and $d_1+d_2\equiv 0\pmod{4}$. Case 1: WLOG $d_1$ is odd and $d_2$ is even. Then $d_2\equiv 0\pmod{4}$. Let $d_2=4s$ where $s$ is odd. Note that $s$ cannot be even since the product cannot be divisible by 8. After dividing the modular equation by 4, we get $1008^o\equiv 1\pmod {(4s+d_1)(sd_1)}, o=2n-1$. Remember that Fermat's LIttle Theorem states that $a^{p-1}\equiv 1\pmod{p}$ if $p\nmid{a}$. There must be a prime $p$ that divides $(4s+d_1)(sd_1)$, and by CRT, that means that $o$ is one less than that $p$. However, $o$ must be odd so the only $p$ that works is $p=2$. Thus, this implies that $(4s+d_1)(sd_1)$ has no divisor of any other prime other than 2, so it must be a power of 2. However, since $d_1$ is odd, it cannot have a factor of 2. We arrive at a contradiction.

Case 2: $d_1, d_2\equiv 1\pmod{2}, d_1+d_2\equiv 0\pmod{4}$

See also

2016 JBMO (Problems • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
1 • 2 • 3 • 4
All JBMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2016_JBMO_Problems/Problem_3&oldid=206224"