# If $x^2 \equiv a \pmod n$, then $x^2 \equiv a \pmod {p_i}$, where $n=p_1^{t_1} \dots p_r^{t_r}$: why?

Now I'm not sure why the following holds:

If $x^2 \equiv a \pmod n$ for some $x \in \mathbb Z$, then $x^2 \equiv a \pmod {p_i}$ for all $i$, where $n=p_1^{t_1} \dots p_r^{t_r}$.

I know that if $a \equiv b \pmod {p_1 \dots p_r}$, then $a \equiv b \pmod {p_i}$ for all $i$, if $p_1, \dots, p_r$ are pairwise relative primes.

-
$k\mid n$ $\land$ $x\equiv y \pmod n$ $\Rightarrow$ $x\equiv y\pmod k$ Can you prove this? Do you see how this implies your claim? –  Martin Sleziak Dec 3 '11 at 12:14
@Martin: What about like this: Let $n=p_1^{t_1} \dots p_r^{t_r}$. Then $p_i∣n$( $n=p_i \cdot N$) and let $a \equiv b\pmod n$ or $a-b=nk \Rightarrow a-b =p_iK$ <=>$a \equiv b \pmod {p_i}$ –  laovultai Dec 3 '11 at 13:03

Lemma: $k\mid n$ $\land$ $x\equiv y \pmod n$ $\Rightarrow$ $x\equiv y\pmod k$

Proof. $x\equiv y \pmod n$ is equivalent to $n\mid x-y$. Since $k\mid n$ and $n\mid x-y$, we get that $k\mid x-y$, i.e. $x\equiv y \pmod k$.

If $p$ is some prime from the prime factorization of $n$, then clearly $p\mid n$. So if $x^2 \equiv a \pmod n$ then, using the above lemma, we have $x^2 \equiv a \pmod p$.

-

It's a congruence form of transitivity of divisibility $\rm\:d\:|\:e\:|\:n\ \Rightarrow\ d\:|\:n\:.\:$ In particular

$\rm\qquad\qquad\qquad\qquad c\:d\ |\ a-b\ \ \Rightarrow\ \ d\ |\ a-b\quad$ which, in the language of congruences, is

$\rm\qquad\qquad a\equiv b\pmod{c\:d}\ \ \Rightarrow\ \ a\equiv b\pmod{d}$

E.g. two integers with equal least significant digit are congruent mod $10\ \Rightarrow$ congruent mod $2$, i.e. they have equal parity (odd or even).

-