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)
 
(2 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>
  
Line 47: Line 48:
 
One way to show this is by checking all 27 possible 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 \equiv 1 (\mod 3)</math> and <math>y \equiv 1 (\mod 3)</math>
 
<math>x \equiv 1 (\mod 3)</math> and <math>y \equiv 1 (\mod 3)</math>
Line 59: Line 60:
 
'''Method 2:''' Using modulo 7
 
'''Method 2:''' Using modulo 7
  
−
<math>xy(x+y) + 4 = 0 \equiv (\mod 7)</math>
+
<math>xy(x+y) + 4 \equiv 0 (\mod 7)</math>
  
−
<math>xy(x+y) = 3 \equiv (\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.
 
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.
 
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"