Let n, m be an element of Z+ and a,b be elements of Z. Suppose that a=b(modn) and a =b(modm) and that (n,m)=1. Prove that a=b(mod nm)
Answer
Z+ means positive integers.
Proof.
(a – b) is divisible by n.
(a – b) = pn for some positive integer p.
(a – b) is divisible by m.
(a – b) = qm for some positive integer q.
Since both m and n divide (a – b) and have no factor in common (from (n,m)=1 ), it means that (a – b) is a multiple of (mn) for m & n each contribute DISTINCT FACTORS into the composition of (a – b). This means (a -b) is divisible by m and n “SIMULTANEOUSLY”.In other words, (mn) divides (a – b).
That is, (a – b) = 0 ( mod mn )
or a=b(mod nm)
QED
STAY CONNECTED