问题及解答

求同余方程 $x^{205}\equiv 3\pmod{1024}$.

[讨论]

这是模为 $2^k$ 的同余式情形. 并且由于 3 是奇数(模2余1), 所以 $x$ 也必是奇数.

Note: $2^k$ 当 $k > 2$ 时没有元根(primitive root).

由于对于任意大于 2 的奇数 $a$ 都满足同余式

\[
a^{\frac{1}{2}\varphi(2^{\alpha})}=a^{2^{\alpha-2}}\equiv 1\pmod{2^\alpha}
\]

因此

\[
a^{\varphi(2^{\alpha})}=a^{2^{\alpha-1}}\equiv 1\pmod{2^\alpha}
\]

\[
(a^{2^{\alpha-1}})^2=a^{2^{\alpha}}\equiv 1\pmod{2^\alpha}
\]

所以对于 $a=3$, $\alpha=10$, 有

\[
3^{2^{10-2}}=3^{2^8}\equiv 1\pmod{2^{10}}
\]

因此,

\[
3^{2^9}\equiv 1\pmod{2^{10}}
\]

\[
3^{2^{10}}\equiv 1\pmod{2^{10}}
\]

这推出

\[
3\cdot3^{2^{10}}=3^{2^{10}+1}=3^{1025}\equiv 3\pmod{2^{10}}
\]

注意到 $3^{1025}=(3^5)^{205}$, 因此原同余方程的解为

\[
x\equiv 3^5=243\pmod{1024}.
\]