2013 Indonesia MO Problems/Problem 6

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$

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

Page

Toolbox

Search

2013 Indonesia MO Problems/Problem 6

Problem

Solution

See Also