Problem 1505

(a) Prove that $2^{2^{m+1}p^k} \equiv 1 \pmod{p^{k+1}}$.

1. Define $a = 2^{2^m}$ and $b = -1$. Note that $a - b = 2^{2^m} - (-1) = 2^{2^m} + 1 = p$, so $p \mid a - b$.
2. Using the Euclidean Algorithm, we find:
$$\gcd(p, ab) = \gcd(2^{2^m} + 1, -2^{2^m}) = \gcd(1, -2^{2^m}) = 1.$$
Thus, $p \mid a - b$ and $\gcd(p, ab) = 1$.
3. Apply the Lifting The Exponent (LTE) Lemma with the prime $p$ as the base:
$$\nu_p(a^{p^k} - b^{p^k}) = \nu_p(p^k) + \nu_p(a - b).$$
4. Since $p$ is odd, $p^k$ is also odd, so $(-1)^{p^k} = -1$. Therefore:
$$\nu_p((2^{2^m})^{p^k} - (-1)^{p^k}) = \nu_p(p^k) + \nu_p(p).$$
5. Simplifying, we get:
$$\nu_p(2^{2^m p^k} + 1) = k + 1.$$
6. Taking modulo $p^{k+1}$, we have:
$$2^{2^m p^k} + 1 \equiv 0 \pmod{p^{k+1}},$$
which implies:
$$2^{2^m p^k} \equiv -1 \pmod{p^{k+1}}.$$
7. Squaring both sides, we get:
$$2^{2 \cdot 2^m p^k} \equiv 1 \pmod{p^{k+1}},$$
or equivalently:
$$2^{2^{m+1} p^k} \equiv 1 \pmod{p^{k+1}}.$$

(b) Prove that $2^{m+1} p^k$ is the smallest positive integer $n$ satisfying $2^n \equiv 1 \pmod{p^{k+1}}$.

1. From part (a), we have shown that $2^{2^{m+1} p^k} \equiv 1 \pmod{p^{k+1}}$. This implies that the order of 2 modulo $p^{k+1}$ divides $2^{m+1} p^k$.
2. Since $2^{2^m p^k} \equiv -1 \not\equiv 1 \pmod{p^{k+1}}$, it follows that $\nu_2(\text{ord}_{p^{k+1}}(2)) = m+1$.
3. Therefore, the order of 2 modulo $p^{k+1}$ must be of the form $2^{m+1} p^i$ for some $i \in \{0, 1, \ldots, k\}$.
4. Apply the LTE Lemma again with $c = 2^{2^{m+1}}$ and $d = 1$:
$$c - d = 2^{2^{m+1}} - 1 = (2^{2^m} + 1)(2^{2^m} - 1) = p(p-2).$$
5. Thus, $c = p(p-2) + d = p(p-2) + 1 = p^2 - 2p + 1 = (p-1)^2$.
6. Since $\gcd(p, cd) = \gcd(p, (p-1)^2) = 1$, we can apply the LTE Lemma:
$$\nu_p(c^{p^i} - d^{p^i}) = \nu_p(p^i) + \nu_p(c - d).$$
7. Substituting $c - d = p(p-2)$, we get:
$$\nu_p(2^{2^{m+1} p^i} - 1) = i + 1.$$
8. Since $\text{ord}_{p^{k+1}}(2) = 2^{m+1} p^i$, it follows that:
$$2^{2^{m+1} p^i} \equiv 1 \pmod{p^{k+1}},$$
implying:
$$\nu_p(2^{2^{m+1} p^i}) \ge k + 1.$$
9. Since $\nu_p(2^{2^{m+1} p^i} - 1) = i + 1$, it follows that $i + 1 \ge k + 1$, or $i = k$ since $i \in \{0, 1, \ldots, k\}$.
10. Hence, we conclude that:
$$\text{ord}_{p^{k+1}}(2) = 2^{m+1} p^k.$$