# Demonstration congruences

Assuming that $m=p_1^{\alpha_1}...p_r^{\alpha_r}$. Show that $$a\equiv b\pmod m\Longleftrightarrow a\equiv b\pmod {p_i^{\alpha_i}},\;i={1,...,r}$$

I always thought very beautiful statements that contain numbers in this way $$x=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}p_4^{\alpha_4}...p_w^{\alpha_w}$$and to be here studying congruences, came across eats this issue, which unfortunately do not even know where to start or what to do ... While statements like these, I can not understand them very easily so I ask YOU DO PLEASE DETAILED ...

I thank you ..

• Start with a simple case: try to show that if $\gcd(c,d)=1$, then $a\equiv b\pmod{cd}$ if and only if $a\equiv b\pmod c$ and $a\equiv b\pmod d$. – Gerry Myerson Oct 6 '13 at 2:05
• @GerryMyerson Sorry, but I can not do such a demonstration. $:'($ – marcelolpjunior Oct 6 '13 at 2:07
• Can you show that if $a\equiv b\pmod{rs}$, then $a\equiv b\pmod r$? – Gerry Myerson Oct 6 '13 at 2:12
• I honestly can not understand. : ( – marcelolpjunior Oct 6 '13 at 2:15
• Yes, I think this as I did above, lol, pretty simple, but I had not realized!! – marcelolpjunior Oct 6 '13 at 2:26

## 3 Answers

Lemma 1: if $c$ and $d$ are coprime and both divide $x$, then their product divides $x$.

Proof: on the hypotheses, $x=cr=ds$ for some integers $r,s$, so $c$ divides $ds$. That, with $c$ being coprime to $d$, implies (by a standard result) that $c$ divides $s$, so $s=ct$ for some integer $t$, so $x=cdt$, so $cd$ divides $x$.

Lemma 2: if $c_1,c_2,\dots,c_r$ are pairwise coprime, and all divide $x$, then their product divides $x$.

Proof: by induction on $r$, with Lemma 1 providing the base of the induction.

Theorem: if $p_1,p_2,\dots,p_r$ are distinct primes, and $m=p_1^{u_1}p_2^{u_2}\times\cdots\times p_r^{u_r}$, and $a\equiv b\pmod{p_i^{u_i}}$ for all $i$, then $a\equiv b\pmod m$.

Proof: the numbers $p_i^{u_i}$ are pairwise coprime, so Lemma 2 applies.

$(\Longrightarrow)\\a\equiv b\pmod m\Longrightarrow a\equiv b\pmod{p_1^{\alpha_1}...p_r^{\alpha_r}}$

Be $m=p_1^{\alpha_1}...p_i^{\alpha_i}...p_r^{\alpha_r}$, with $i=1,...,r$ then, knowing that $$\text{If}\;\;(p_i^{\alpha_i},p_j^{\alpha_j})=1\;\text{with}\;\;i\neq j\;\;\text{and}\;\;j=1,...,r$$As $a\equiv b\pmod m$, then $m\mid (a-b)$, implies $p_1^{\alpha_1}...p_r^{\alpha_r}\mid (a-b)$, implies $a-b=p_1^{\alpha_1}...p_r^{\alpha_r}\cdot k$ with $k\in\mathbb{N}$, then$$a-b=p_i^{\alpha_i}(p_1^{\alpha_1}...p_r^{\alpha_r}\cdot k)\Longrightarrow p_i^{\alpha_i}\mid (a-b)\Longrightarrow a\equiv b\pmod {p_i^{\alpha_i}}$$$\Box$Correct?

Hint: Show that if $(n_1,n_2)=1$, then $n_1\cdot n_2|(a-b)$ if and only if $n_1|(a-b)$ and $n_2|(a-b)$.