Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
$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

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

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.