Chinese Remainder Theorem: A Powerful Tool in Number Theory

[calvino]

Chinese Remainder Theorem!

I'm pretty sure that the following is in fact the Chinese remainder Theorem:

If n= (m1)(m2)...(mk) [basically, product of m's (k of them)]
where each m is relatively prime in pairs, then there is an isomorphism from Zn to ( Zm1 X Zm2 X ... X Zmk). Zn is the integers modulo n.

All the proofs of the chinese remainder theorem I found searching online, are either the ones that focus on modulo, or focus more on ideals (and proving a certain mapping is an isomorphism). How do I go about proving the statement up there?

 

[AKG]

Every time I've seen the CRT, it has to do with modulos, i.e. it is more focused on arithmetic, not groups. In fact, this fact about groups that you're trying to prove typically uses the arithmetic fact that is the CRT to construct the desired isomorphism. The map from Zn to the product group is natural. It's easy to show this map is homomorphic and injective. Surjectivity follows immediately from the CRT.

 

[calvino]

I forgot to add one thing. The isomorphism in the conclusion is a ring isomorphism...


Ok, well I somewhat see what you're saying AKG. A little more studying and I should get it. What confuses me though, is that relative primality is not transitive. So I'm not sure IF or HOW i can even get to defining the mapping properly. I guess I'm not sure what you mean by the mapping being natural.

 

[AKG]

The map is a group isomorphism, where the proof is made easy by the CRT, so this map preserves the additive properties. I haven't tried to do it, but you can check whether or not this map also preserves multiplication, thereby deciding whether it is a ring isomorphism.

But first, you need to know what the map is. If m and n are relatively prime, then the map from Zmn to Zm x Zn is defined by:

$$x (\mbox{mod }mn) \mapsto (x (\mbox{mod }m), x (\mbox{mod }n))$$

So take m = 3, n = 2. We get:

$$0 \mapsto (0,0)$$
$$1 \mapsto (1,1)$$
$$2 \mapsto (2,0)$$
$$3 \mapsto (0,1)$$
$$4 \mapsto (1,0)$$
$$5 \mapsto (2,1)$$

 

[matt grime]

What confuses me though, is that relative primality is not transitive.

What has this to do with anything?

Given Z/mZ there is only one possible way you can even begin to write down a map to Z/aZ x Z/bZ x... Z/cZ, and it sends x to (x,x,..,x).

If a,b,..c divide m this map is well defined.

If m=a*b*..*c and a,b,..,c are pairwise coprime then this map is invertible by the chinese remainder theorem.

In fact you don't even strictly need this: it is injective and counting elements tells you it is therefore an bijection.

It is easy to show it is also a homomorphism in this case.

 

[jaiez]

I have these two questions in discrete mathematics and I need your help to answer it….
Proof that ∀x⇁p(x)≡⇁∃x p(x)
And
Proof that ⇁∀xp(x)≡∃x⇁ p(x)
Let R be the relation on the set {1,2,3,4,5} containing the order pairs(1,1) ,(1,2) (1,3) ,(2,3) (2,4) ,(3,1) (3,4) ,(3,5) ,(4,2) (4,5) ,(5,1) (5,2) ,and(5,4),Find
R^3
R^4
R^5