1
$\begingroup$

I was reading elementary number theory when I came across the theorem that $ a≡b \pmod{N}$ and $N=nm$ implies that $a\equiv b\pmod{m}$. And as a consequence of it, $a ≡ b \pmod{r}$ and $a \equiv b \pmod{s} \implies a \equiv b \pmod{ lcm(r,s)}$. But I could not think of a proof of it. Could some one please help me with it? Thanks

$\endgroup$

3 Answers 3

0
$\begingroup$

Let $n_1=r\cdot s_1,n_2=r\cdot s_2$ such that $(s_1,s_2)=1\implies (n_1,n_2)=r$ and $$ lcm(n_1,n_2)=\frac{n_1\cdot n_2}{(n_1,n_2)}=r\cdot s_1\cdot s_2$$

As $$n_1\mid (a-b)\implies \frac{a-b}{n_1}=I_1$$ where $I_1$ is some integer.

So, $$a-b=n_1\cdot I_1=r\cdot s_1\cdot I_1$$

Similarly, $$a-b=n_2\cdot I_2=r\cdot s_2\cdot I_2$$ where $I_2$ is some integer.

$$\implies r\cdot s_1\cdot I_1=a-b=r\cdot s_2\cdot I_2$$

So, $$s_1\cdot I_1=s_2\cdot I_2\implies \frac{s_1\cdot I_1}{s_2}=I_2$$ which is an integer.

So, $s_2\mid I_1$ as $(s_1,s_2)=1\implies I_1=s_2\cdot I_3$ where $I_3$ is some integer.

So, $$a-b=n_1\cdot I_1=r\cdot s_1\cdot I_1=r\cdot s_1\cdot s_2\cdot I_3=lcm(n_1,n_2)\cdot I_3$$

$$\frac{a-b}{lcm(n_1,n_2)}=I_3$$ which is an integer.

$\endgroup$
0
$\begingroup$

Hint: There exist integers $r_1, s_1$ such that $r_1 \mid r$ and $s_i \mid s$, $\gcd(r_1, s_1)=1$ and $r_1 s_1 = lcm(r_1, s_1)$. [Think of the prime factorization form for GCD/LCM.]

Thus, $a \equiv b \pmod{r_1}, a\equiv b \pmod{s_1}$. Hence $a \equiv b \pmod{r_1 s_1}$.

$\endgroup$
0
$\begingroup$

Conceptually it is quite simple. The set M of all common multiples of $n_1,n_2$ is a nonempty set of integers closed under subtraction, therefore every element of M is a multiple of its least positive element $ = \rm{lcm}(n_1,n_2).\,$ In particular, $a-b\,$ is a multiple of $\,\rm{lcm}(n_1,n_2).$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .