suppose a = 0 (mod n), and a = b (mod m)
n and m are prime. Is a = b (mod nm)?

$2\equiv 0$ (mod 2) and $2\equiv 5$ (mod 3), but $2\backslash nequiv5$ modulo 6

Kerwin

Ok suppose a = b (mod n) and a=b (mod m)
then does a = b (mod nm) if nm are prime and n,m don't divide a? I left this condition out first.

Hello, Neil.

In this case, if n,m are coprime, the answer is yes.

Proof:
n|a-b, so a-b=kn for some integer k.
m|a-b, so m|kn.
Since m,n coprime, hcf(m,n)=1.
Hence m|k gives k=cm
So a-b=cmn, which is divisible by mn.

Kerwin

I thought as much. Now, suppose a=0 mod n and a=b mod m (n,m still coprime), and n divides b. Does a=b (mod nm)?

I think so, because if a=0, then a=b mod n (because a divides b). Then we use your proof to get the result!

This can be greatly simplified if you deal with the difference between a and b. Call u = a - b. Now u = 0 (mod n) as you have given. Also u = 0 (mod m) because both a and b divide by m. So what you're asking is effectively:

If u is a multiple of m and n (m and n are coprime) then is u necessarily a multiple of mn?

And the answer is yes!
m and n don't share any prime factors, yet both must have their prime factors present in u. Therefore u includes all the prime factors of both m and n, and therefore it is a multiple of mn.

Not a bad question - I wonder if this result has a name.

Michael

Isn't what you're asking just a special case of the proof above with $a\equiv 0\equiv b$ (mod $n$)?

Kerwin

Michael: Yes, these are the lines along which I first proved it, and then changed it to the small proof I gave, using the result that I theorised and Kerwin proved. The name of this result is not particular; it is part of a more general idea called the Chinese remainder theorem, which I can't be bothered to explain here!

Kerwin: Yes! The crucial (and once discovered, unbelievably obvious) step was to say that if n divides b, and a = 0 mod n [ie n divides a as well] then a = b (mod n) is one way of putting it.

Just to state our result again:

If a=0 mod n and a=b mod m, and n divides b, (with n,m coprime), then a=b mod nm.

See if you can have a go at my Fibonacci thing . It's sort of related!

Thanks,

Neil M