2
$\begingroup$

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.

  • 0
    @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}$2011-12-03

2 Answers 2

1

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

2

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