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 "2013 Indonesia MO Problems/Problem 6"

(Created page with "==Problem== Suppose <math>p > 3</math> is a prime number and <cmath>S = \sum_{2 \le i < j < k \le p-1} ijk</cmath> Prove that <math>S+1</math> is divisible by <math>p</math>....")
 
Line 1: Line 1:
 
==Problem==
 
==Problem==
  
−
Suppose <math>p > 3</math> is a prime number and
+
A positive integer <math>n</math> is called "strong" if there exists a positive integer <math>x</math> such that <math>x^{nx} + 1</math> is divisible by <math>2^n</math>.
−
<cmath>S = \sum_{2 \le i < j < k \le p-1} ijk</cmath>
+
 
−
Prove that <math>S+1</math> is divisible by <math>p</math>.
+
a. Prove that <math>2013</math> is strong.
 +
 
 +
b. If <math>m</math> is strong, determine the smallest <math>y</math> (in terms of <math>m</math>) such that <math>y^{my} + 1</math> is divisible by <math>2^m</math>.
  
 
==Solution==
 
==Solution==
  
−
if you let <math>j</math> be constant, you can think of it as summing for each <math>i</math>, <math>\sum^{p-1}_{k=j+1}</math>, and since its for all <math>i</math> you can add another sum to get <math>\sum^{j-1}_{i=2}\sum^{p-1}_{k=j+1}</math>, and for all <math>j</math> we can add another sum, to get <math>\sum_{2\leq i<j<k\le p-1}ijk=\sum^{p-2}_{j=2}\sum^{j-1}_{i=2}\sum^{p-1}_{k=j+1}ijk</math>
+
a. Take <math>x=2^{2013}-1</math>, notice how <math>x</math> is odd, <math>(2^{2013}-1)^{(2^{2013}-1)2013}+1\equiv -1^{\text{some odd number}}+1\equiv -1+1\equiv 0\mod 2^{2013}</math> so its divisible
−
<cmath>\sum^{p-2}_{j=2}\sum^{j-1}_{i=2}\sum^{p-1}_{k=j+1}ijk</cmath>
+
 
−
<cmath>\sum^{p-2}_{j=2}\sum^{j-1}_{i=2}ij\sum^{p-1}_{k=j+1}k</cmath>
+
b. Notice how <math>m</math> is always odd as if it is even then even+odd=odd and cant be divisible by 2^m. By LTE, <math>v_{2}(y^{my}+1^{my})=v_{2}(y+1)\geq m</math> as it is divisible by 2^m, and the smallest <math>y</math> is <math>2^m-1</math>
−
<cmath>\sum^{p-2}_{j=2}\sum^{j-1}_{i=2}ij\left(\frac{(p-j-1)(p+j)}{2}\right)</cmath>
 
−
<cmath>\frac{1}{2}\sum^{p-2}_{j=2}\sum^{j-1}_{i=2}i(j(p-j-1)(p+j))</cmath>
 
−
<cmath>\frac{1}{2}\sum^{p-2}_{j=2}\frac{(j+1)(j-2)(j(p-j-1)(p+j))}{2}</cmath>
 
−
<cmath>\frac{1}{4}\sum^{p-2}_{j=2}(j+1)(j-2)(j(p-j-1)(p+j))</cmath>
 
−
<cmath>\frac{1}{4}\sum^{p-2}_{j=2}-j^5+j^3p^2-j^3p+3j^3-j^2p^2+j^2p+2j^2-2jp^2+2jp</cmath>
 
−
<cmath>\frac{1}{4}(\sum^{p-2}_{j=2}-j^5+(p^2-p+3)\sum^{p-2}_{j=2}j^3+(-p^2+p+2)\sum^{p-2}_{j=2}j^2-(2p^2-2p)\sum^{p-2}_{j=2}j)</cmath>
 
−
<cmath>\frac{1}{4}(-\frac{2n^6+6n^5+5n^4-n^2}{12}+(p^2-p+3)\frac{(p-2)^2(p-1)^2}{4}-(p^2-p+3)+(-p^2+p+2)\frac{(p-2)(p-1)(2p-1)}{6}+(p^2-p-2)-(2p^2-2p)\frac{(p-1)(p-2)}{2}+(2p^2-2p)</cmath>
 
−
<cmath>\frac{1}{48}(p^6-7p^5+11p^4+3p^3+12p^2-20p-48)=S</cmath>
 
−
<cmath>S+1=\frac{1}{48}(p^6-7p^5+11p^4+3p^3+12p^2-20p-48)+1=\frac{p}{48}(p^5-7p^4+11p^3+3p^2+12p-20)</cmath>
 
−
since it has a factor pf <math>p</math>, we need to prove <math>\frac{p^5-7p^4+11p^3+3p^2+12p-20}{48}</math> is always an integer, for prime <math>p>3</math> <math>p\mod 6\equiv 1\text{ or }5</math>, so let <math>p=6k+1</math> and <math>p=6k+5</math>
 
−
for the first case, you get <math>\frac{24k(324k^4+108k^3-63k^2+6k+7)}{48}</math> and for the second you get <math>\frac{24(3k+2)(108k^4+252k^3+195k^2+54k+5)}{48}</math>, notice how both of these are always integers, thus it is proven <math>p</math> divides <math>S+1</math>
 
  
 
==See Also==
 
==See Also==

Revision as of 19:48, 26 December 2024

Problem

A positive integer $n$ is called "strong" if there exists a positive integer $x$ such that $x^{nx} + 1$ is divisible by $2^n$.

a. Prove that $2013$ is strong.

b. If $m$ is strong, determine the smallest $y$ (in terms of $m$) such that $y^{my} + 1$ is divisible by $2^m$.

Solution

a. Take $x=2^{2013}-1$, notice how $x$ is odd, $(2^{2013}-1)^{(2^{2013}-1)2013}+1\equiv -1^{\text{some odd number}}+1\equiv -1+1\equiv 0\mod 2^{2013}$ so its divisible

b. Notice how $m$ is always odd as if it is even then even+odd=odd and cant be divisible by 2^m. By LTE, $v_{2}(y^{my}+1^{my})=v_{2}(y+1)\geq m$ as it is divisible by 2^m, and the smallest $y$ is $2^m-1$

See Also

2013 Indonesia MO (Problems)
Preceded by
Problem 3 		1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 Followed by
Problem 5
All Indonesia MO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_Indonesia_MO_Problems/Problem_6&oldid=237954"