If a number is a square modulo $n$, then it is also a square modulo any of $n$'s factors 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$$
 A: 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$.
A: Hint: $ $ note that $\ a\ $ is a square mod $\, n\iff\ f(x) = x^2-a\ $ has a root mod $\, n.\, $
But a root mod $\, n\, $ of a polynomial $\ f(x)\in \Bbb Z[x]\ $ persists as a root mod $\, k\,$ for  $\, k\mid n\,$
because $\ \ f(b)\equiv 0\pmod{n}\ \Rightarrow\ n = jk\mid f(b)\ \Rightarrow\ k\mid f(b)\ \Rightarrow\ f(b)\equiv 0\pmod{k} $
As another example, the linear analog of square preservation is fraction preservation. For example, if $\ ab = 2k- 1\ $ then, mod $\, ab,\,$ we have $\, 2k\equiv 1\ $ so $\, 1/2 \equiv k,\,$ and this congruence remains true both mod $\,a\,$ and mod $\,b.$  
More generally, any solution of an equation in an equational algebraic structure remains a solution in any modular (homomorphic) image of the structure.
