Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

gcd(m,n) and modular arithmetic

Name: Anonymous 2009-09-16 2:41

"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.

Name: Anonymous 2009-09-17 22:49

>>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.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List