China Western Mathematical Olympiad

We want to prove that $2^{2^{m+1}}{p}^k=p^{k+1}{t}_k+1$ for some integer $t_k$ not divisible by $p$. We proceed by induction on $k$.

When $k=0$, it follows from $2^{2^m}=p-1$ that $2^{2^m}=(p-1{)}^2=p(p-2)+1$, in this case, $t_0=p-2$.

For inductive step, suppose that $2^{2^{m+1}}{p}^k=p^{k+1}{t}_k+1$ where $k\ge 0$ and $p\nmid t_k$, then $$\begin{array}{rl}{2}^{2^{m+1}}{p}^{k+1}& =(2^{2^{m+1}}{p}^k)p=(p^{k+1}{t}_k+1{)}^p\\ & =\sum _{s=0}^p\left(\genfrac{}{}{0ex}{}{p}{s}\right)(p^{k+1}{t}_k{)}^s\\ & =1+p\cdot p^{k+1}{t}_k+\frac{p(p-1)}{2}(p^{k+1}{t}_k{)}^2+\sum _{s=3}^p(\genfrac{}{}{0ex}{}{p}{s})(p^{k+1}{t}_k{)}^s.\end{array}$$ As $k\ge 0$, then for any $s\ge 2$, we have $(k+1)s\ge 2(k+1)=2k+2\ge k+2$, so $2^{2^{m+1}}{p}^{k+1}=p^{k+2}{t}_{k+1}+1$, where $t_{k+1}\in {\mathbb{Z}}_{+}$ and $p\nmid t_{k+1}$. It follows from mathematical induction that (a) holds.

Next, we prove (b). Write $2^{m+1}{p}^k=n\ell +r$, where $\ell ,r\in \mathbb{Z}$ and $0\le r<n$. Then it follows from (a) that $1\equiv 2^{2^{m+1}}{p}^k\equiv 2^{n\ell +r}\equiv (2^n{)}^{\ell }\cdot 2^r\equiv 2^r(\mathrm{mod}{p}^{k+1})$. As $0\le r<n$, it follows from the definition of $n$ that $r=0$, i.e., $n\mid 2^{m+1}{p}^k$. By the Fundamental Theorem of Arithmetic, $n=2^t{p}^s$. If $t\le m$, then $2^{2^m}{p}^k=(2^{2^t}{p}^k{)}^{2^{m-t}}\equiv 1(\mathrm{mod}p)$. On the other hand, $2^{2^m}{p}^k=(2^{2^m}{)}^{p^k}\equiv (-1{)}^{p^k}\equiv -1(\mathrm{mod}p)$, which is a contradiction, and hence $t=m+1$, i.e., $n=2^{m+1}{p}^s$. $\square$