Question

Let
m1, m2
be positive integers with . Prove that the system of congruences $x\equiv r_{1}(mod m_{1}), x\equiv r_{2}(mod m_{2})$ has a solution if and only if $r_{1} \equiv r_{2}(mod d)$ .

Answer 1

we have:

we have: x equive r_1(modm1) or we can write x = r1 + m1 times A where a is an integer Similarly x equive r2 (modm2) or we can write x= r2 + m1 * B where B is some integer What we need to prove is r_1 equive r2(modd) or r1 = r2+d*(C) where C is some integer here x = m1 times A + r1 ........equ1 x = m2 times B + r2 ........ equ2 Subtracting equation 2 from 1, we get 0 = m1 times A - m2 times B + r1 - r2 or r1 = r2 - (m1 times A - m2 times B)............. equ3 Now we also have: gcd (m1, m2) = d thus two numbers m1 and m2 can be expressed as a integral multiple of d as m1 = P times d where p is an integer.............................................eq4 and m2 = Q times d where q is an integer................................................eq5
or we can write where a is an integer

Similarly

$x \equiv r2(mod m2)$ or we can write x= r2 + m1 * B where B is some integer

What we need to prove is

$r1 \equiv r2(mod d)$ or r1 = r2+d*(C) where C is some integer

here

...................eq1

...................eq2

Subtracting equation 2 from 1, we get

or

.......................................eq3

Now we also have :

thus two numbers m1 and m2 can be expressed as a integral multiple of d as

where p is an integer.............................................eq4

and

where q is an integer................................................eq5

and also since , d divides m1 and m2 , it also divides m1-m2.

Thus

from eq 3 , eq4 and eq 5, we get

or

or

where Z =

thus

r1 = r2 + Z where z is d*(P*A - Q*B) .

which is what we have to prove that is

r1 = r2 + d*C where C = (P*A - Q*B).

Hence proved