[Math] If a number is a square modulo $n$, then it is also a square modulo any of $n$’s factors

elementary-number-theory

Say we have $a \equiv x^2 \bmod n$. How would we prove that this implies:

$$\forall \text{ prime }p_i\text{ such that }\,p_i\mid n,\;\exists y\,\text{ such that }\, a \equiv y^2 \bmod p_i$$

Best Answer

If $n$ is a natural number and $a$ and $b$ are integers, when we say $$a\equiv b\bmod n,$$ we just mean that $n$ divides $b-a$. This clearly implies that any factor of $n$ also divides $b-a$, so that if $m$ is any factor of $n$, we also have $a\equiv b\bmod m$.

Thus, if we start with our integer $a$, and there exists an integer $x$ such that $a\equiv x^2\bmod n$, we must also have $a\equiv x^2\bmod m$ for any number $m$ that divides $n$, and in particular, $a\equiv x^2\bmod p$ for any prime factor $p$ of $n$.

Related Question