Question

x^2 ≡ 1 mod p, p - простое. Почему x ≡ ±1 mod p?

Answer 1

$x^{2} \equiv 1\mod p\Leftrightarrow x^2-1\equiv 0\mod p\Leftrightarrow (x-1)(x+1)\equiv 0\mod p$

Полученное сравнение равносильно утверждению: $(x-1)(x+1)$ делится на $p$.

Т.к. $p$ простое, то хотя бы один из множителей $(x-1)$ и $(x+1)$ делится на $p$, что и означает, что $x\equiv \pm 1\mod p$.

Ч.т.д.