1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Gerry Myerson Oct 6 '13 at 2:05
  • $\begingroup$ @GerryMyerson Sorry, but I can not do such a demonstration. $:'($ $\endgroup$ – marcelolpjunior Oct 6 '13 at 2:07
  • $\begingroup$ Can you show that if $a\equiv b\pmod{rs}$, then $a\equiv b\pmod r$? $\endgroup$ – Gerry Myerson Oct 6 '13 at 2:12
  • $\begingroup$ I honestly can not understand. : ( $\endgroup$ – marcelolpjunior Oct 6 '13 at 2:15
  • 2
    $\begingroup$ Yes, I think this as I did above, lol, pretty simple, but I had not realized!! $\endgroup$ – marcelolpjunior Oct 6 '13 at 2:26
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

$(\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?

$\endgroup$
-1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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