Korean Mathematical Olympiad Final Round

(1) An arbitrary element of $A_m$ can be written in the form $m+1+k(2m+1)$, where $k=0,1,2,\dots$. Putting $ϵ=0$ or $1$, $$m+1+k(2m+1)=2^a+ϵ⟺2^a\equiv m+1-ϵ(\mathrm{mod}2m+1)$$ $$⟺2^{a+1}\equiv 1-2ϵ(\mathrm{mod}2m+1)$$ $$⟺2^{a+1}\equiv \{\begin{array}{ll}1& (\text{mod }2m+1)\\ -1& (\text{mod }2m+1)\end{array}\text{if }ϵ=0,\text{ if }ϵ=1.$$ Let $r$ be the smallest positive integer $t$ satisfying $2^t\equiv 1(\mathrm{mod}2m+1)$, that is, $r={\text{ord}}_{2m+1}(2)$. Observe that $r>2$ because $2m+1\ge 5$,

i) $r\le m$: Since $1<r-1<m$, we may take $a:=r-1$. Then $1<a<m$ and $$2^{a+1}\equiv 1(\mathrm{mod}2m+1)⟺\begin{array}{l}(ϵ=0)\\ 2^a\in A_m.\end{array}$$

ii) $r>m$: Since $2m+1$ is odd, $\varphi (2m+1)$ is even. Furthermore, $$r|\varphi (2m+1),\varphi (2m+1)\le 2m⟹r=\varphi (2m+1).$$ That is, $2$ is a primitive root (mod $2m+1$). Thus, $2^{r/2}\equiv -1(\mathrm{mod}2m+1)$. This is because $$\begin{array}{rl}\exists s(0<s<r),2^s\equiv -1(\mathrm{mod}2m+1)& ⟹2^{2s}\equiv 1(\mathrm{mod}2m+1)\\ & ⟹r\mid 2s,0<2s<2r\\ & ⟹2s=r.\end{array}$$ Take $a:=(r/2)-1$. Then, from $4\le r=\varphi (2m+1)\le 2m$, we obtain $1\le a<m$ and $$2^{a+1}\equiv -1(\mathrm{mod}2m+1)\stackrel{(ϵ=1)}{⟹}{2}^a+1\in A_m.$$

(2) For a given $m$, we observed that $2^{r-1}\in A_m$ in (1) above, where $r={\text{ord}}_{2m+1}(2)$. Furthermore, it is clear that the smallest $a$, for which $2^a\in A_m$, holds, is $a_0=r-1$.

i) $r$ is even and $2^{r/2}\equiv -1(\mathrm{mod}2m+1)$: In this case, $2^{(r/2)-1}+1\in A_m$ holds, and the smallest $b$ for which $2^b+1\in A_m$ holds is $b_0=(r/2)-1$.

ii) $r$ is even and $2^{r/2}\not\equiv -1(\mathrm{mod}2m+1)$: Let's assume that there exists an $s$ with $0<s<r$ satisfying $2^s\equiv -1(\mathrm{mod}2m+1)$. Then from $2^{2s}\equiv 1(\mathrm{mod}2m+1)$, we get $r\mid 2s$. Since $2s\not\equiv r(\mathrm{mod}2r)$, $2s\ge 3r$, that is, $s>r$, which is a contradiction. Therefore, in this case, $A_m$ contains no element of the form $2^b+1$.

iii) $r$ is odd: Let's assume that there exists an $s$ with $0<s<r$ satisfying $2^s\equiv -1(\mathrm{mod}2m+1)$. Then from $2^{2s}\equiv 1(\mathrm{mod}2m+1)$, we get $r\mid 2s$ and hence $r\mid s$ because $r$ is odd. But this is absurd since $0<s<r$. Therefore, in this case again, $A_m$ contains no element of the form $2^b+1$.

Combining (i~iii), we may conclude that $$b_0=\frac{a_0+1}{2}-1=\frac{a_0-1}{2}.\square$$

Let $x,y$ be the smallest positive integers satisfying $$2^x\equiv -1(\mathrm{mod}2m+1),2^y\equiv 1(\mathrm{mod}2m+1).$$ Clearly, $0<x<y\le 2x$. Assume that $y=xq+r$ ($0\le r<x$). Since $$1\equiv 2^y\equiv (2^x{)}^q{2}^r\equiv (-1{)}^q{2}^r(\mathrm{mod}2m+1).$$ $q$ should be even. Hence $q=2$ and $r=0$. This completes the proof. $\square$