Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
$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}$ – alvoutila Dec 3 '11 at 13:03
up vote 2 down vote accepted

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$.

share|cite|improve this answer

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).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.