Сравнения по составному модулю

Предложение. Если $p \in \mathbb {P}\backslash \{ 2\}$, то $\exists x\colon x^2 \equiv a \pmod{p^\alpha } \iff \exists x\colon x^2 \equiv a \pmod p$.

$\blacktriangle$
($\Rightarrow$)
Если $x^2 \equiv a\ (p^\alpha )$ имеет решение $x_0$, то $x_0^2 - a \equiv 0\ (p^\alpha ) \Rightarrow x_0^2 - a \equiv 0\ (p)$.

($\Leftarrow$)
Будем доказывать $\alpha = 2$ (случай $\alpha > 2$ аналогичен).

Рассмотрим $x^2 \equiv a\ (p^2)$.

Пусть $\tilde{x}$ — решение $x^2 \equiv a\ (p)$.

Пусть $x = \tilde{x} + tp \equiv \tilde{x}\ (p)$.

$(\tilde{x} + tp)^2 - a \equiv 0\ (p^2)$.

$\tilde{x}^2 - a + 2tp\tilde{x} + tp^2 \equiv 0\ (p^2)$.

$\tilde{x}^2 - a + 2tp\tilde{x} \equiv 0\ (p^2)$.

$\tilde{x}^2 - a$ представим в виде $lp$ (т.к. $\tilde x^2 \equiv a\ (p)$).

$\newcommand{\divby}{\mathop{\smash{\vdots}}}$
$lp + 2t\tilde{x}p \divby p^2$.

$l + 2t\tilde{x} \equiv 0\ (p)$.

$2\tilde{x}t \equiv -l\ (p)$. $2\tilde{x} \neq 0 \Rightarrow$ уравнение имеет решение $t$ (если $p$ — чётно, то решения может не существовать).

Так как все переходы эквивалентны, то решение будет решением $(\tilde{x} + tp)^2 - a \equiv 0\ (p^2)$.
$\blacksquare$

Предложение. Если $a \equiv 1\ (8)$, то $a$ — вычет mod $2^\alpha$.