gcd(m,n) and modular arithmetic

"If gcd(m,n) = 1, show that for any pair of integers a and b there exists an integer x such that x ≡ a mod m and x ≡ b mod n."

I'm having trouble interpreting this problem. When I look at this, I think, for example:

m = 7
n = 11
a = 6
b = 8

and

x ≡ 6 mod 7 -> 6
x ≡ 8 mod 11 -> 8

I'm not sure what I'm doing wrong. If someone could show me an example of integers m, n, a, b where the problem works I think I can finish the problem. Any response is appreciated.

x ≡ 41 mod 77 for that

chinese remainder theorem

yep crt

Let mp+nq=1, then

amp+anq = a
bmp+bnq = b

So

anq = a (mod m)
bmp = b (mod n)

>>1
"x ≡ a mod m" is a weird notation. It does NOT mean that x is equivalent to the modulo operator applied to a and m. Instead, it means that the equivalence "x ≡ a" holds if we consider both x and a modulo m. In effect, it means that "modulus(x, m) ≡ modulus(a, m)". You're interpreting it as "x ≡ modulus(a, m)".

>>6
Gauss invented the notation.

Gauss had triple your IQ.

Therefore, shut the hell up.

>>6

It means "congruent", not "equivalent".

and >>7 was right on the ball.

http://en.wikipedia.org/wiki/Euclid%27s_algorithm#Description

>>6
You're using \equiv as if it meant equality.

>>5
I think the final answer we want is
anq + bmp

Having proved the 1st half of the CRT, we then (if we want to) need to prove that this number x is unique mod mn

>>7
Your point? Newtons notation sucked too, why couldn't Gauss's?

>>12

"Equivalence modulo m" (or more generally "equivalence modulo an ideal" in some ring) just means that the images of two numbers in the factor ring of Z by mZ under the natural reduction homomorphism are equal.  So if \phi_m : \mathbb{Z} \rightarrow \mathbb{Z} / m\mathbb{Z} is the natural reduction homomorphism, saying " a \equiv b \pmod m " is the same as saying \phi_m (a) = \phi_m (b), where equality is understood to be in the ring which is the target of \phi_m.

So basically, some way or another, you need to keep track of which ring you're working in (equivalently the modulus), and the "≡ (mod m)" notation is at least as convenient as any other that anyone's come up with, and at this point there doesn't seem to be any reason to change.

>>11
Err, yeah.  I forgot that last bit. ^^

>>13
I never said that it should be changed, or that the notation isn't good; just that it is a weird notation - one that OP might not parse correctly on the first attempt.