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 $\epsilon = 0$ or $1$,
$$m+1+k(2m+1) = 2^a + \epsilon \iff 2^a \equiv m+1-\epsilon \pmod{2m+1}$$
$$\iff 2^{a+1} \equiv 1-2\epsilon \pmod{2m+1}$$
$$\iff 2^{a+1} \equiv \begin{cases} 1 & (\text{mod } 2m+1) \\ -1 & (\text{mod } 2m+1) \end{cases} \quad \text{if } \epsilon=0, \text{ if } \epsilon=1.$$
Let $r$ be the smallest positive integer $t$ satisfying $2^t \equiv 1 \pmod{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 \pmod{2m+1} \iff \begin{array}{l} (\epsilon=0) \\ 2^a \in A_m. \end{array}$$

ii) $r > m$:
Since $2m+1$ is odd, $\phi(2m+1)$ is even. Furthermore,
$$r | \phi(2m+1), \phi(2m+1) \le 2m \implies r = \phi(2m+1).$$
That is, $2$ is a primitive root (mod $2m + 1$). Thus, $2^{r/2} \equiv -1 \pmod{2m+1}$. This is because
$$\begin{align*} \exists s (0 < s < r), 2^s \equiv -1 \pmod{2m+1} &\implies 2^{2s} \equiv 1 \pmod{2m+1} \\ &\implies r \mid 2s, 0 < 2s < 2r \\ &\implies 2s = r. \end{align*}$$
Take $a := (r/2) - 1$. Then, from $4 \le r = \phi(2m+1) \le 2m$, we obtain $1 \le a < m$ and
$$2^{a+1} \equiv -1 \pmod{2m+1} \quad \stackrel{(\epsilon=1)}{\implies} \quad 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 \pmod{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 \pmod{2m+1}$:
Let's assume that there exists an $s$ with $0 < s < r$ satisfying $2^s \equiv -1 \pmod{2m+1}$. Then from $2^{2s} \equiv 1 \pmod{2m+1}$, we get $r \mid 2s$. Since $2s \not\equiv r \pmod{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 \pmod{2m+1}$. Then from $2^{2s} \equiv 1 \pmod{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}. \quad \square$$

Let $x, y$ be the smallest positive integers satisfying
$$2^x \equiv -1 \pmod{2m+1}, \quad 2^y \equiv 1 \pmod{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 \pmod{2m+1}.$$
$q$ should be even. Hence $q = 2$ and $r = 0$. This completes the proof. $\square$