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"
(→‎Solution)
 
(One intermediate revision by the same user not shown)
Line 11: Line 11:
 
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
 
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
  
−
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>
+
b. Notice how <math>y</math> is always odd as if it is even then even+odd=odd and cant be divisible by 2^m, and <math>m</math> is always odd as if it is even <math>y^{my}=(y^{ny})^2=1\mod 4</math>, <math>1+1=0\mod 4</math> which is not true because if m=1 then it is odd. 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>
  
 
==See Also==
 
==See Also==

Latest revision as of 19:54, 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 $y$ is always odd as if it is even then even+odd=odd and cant be divisible by 2^m, and $m$ is always odd as if it is even $y^{my}=(y^{ny})^2=1\mod 4$, $1+1=0\mod 4$ which is not true because if m=1 then it is odd. 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=237956"