Talk:Chinese remainder theorem

From Wikipedia, the free encyclopedia

You have new messages (last change).

Contents

[edit] Domains

I wonder how general this theorem is true? It works for principal ideal domains, but is it still true for unique factorization domains? --AxelBoldt

Just noticed that it is not true for UFD's: the map F[X,Y]/(XY) -> F[Y] x F[X] is not surjective (F some field). --AxelBoldt

[edit] Versions for more than two numbers

I'd like to say that the result is true for three or more numbers in the place of a and b (pairwise coprime), but I'm having difficulty phrasing this without making it seem more complicated than it is. --Matthew Woodcraft

I added the versions for more than two factors. The description of how to solve the congruencies and of the inverse isomorphisms are still missing. --AxelBoldt

This is a lot better than my writings. --Georg Muntingh

[edit] Euclidean algorithm

I learned it to be true for any Euclidean ring. In that case one is able to perform the Euclidean Algorithm. Is one always able to perform the Euclidean Algorithm on principal ideal domains? -- Georg Muntingh

You can't always perform the Euclidean Algorithm in principal ideal domains, but you don't need this for the Chinese Remainder Theorem. In a PID, if x and y have gcd 1, then xyR = xR ∩ yR and xR + yR = R. So the Chinese Remainder Theorem for PIDs follows from the version of the theorem for arbitrary rings, which I've now added to the article. (We still need to add the Chinese Remainder Theorem for integers, and this should be dealt with first, without mentioning isomorphisms and factor rings.) --Zundark, 2002 Jan 12

[edit] More practical approach

What I want is a more practical (not theoretical) approach to this theorem. For instance, let's say I have some arcade tickets. I don't know how many I have, but when I count them out by 10's I have 8 left over; when I count them out by 14's I have 6 left over, and when I count them out by 18's I have 12 left over. What is the set of possible numbers of tickets I might have? User:208.58.249.208

Yup, pretty practical that one. Happens to me all the time. AxelBoldt 05:49 Feb 19, 2003 (UTC)
Have you ever noticed, when counting out a large number of objects, that it helps to count modulo a small number? Besides, I might add, who uses, or even understands, the technical mumbo-jumbo in this article? User:208.58.249.145
Mathematicians, of course! —Lowellian (reply) 04:32, 30 September 2005 (UTC)

[edit] More generalized form should be added

The section on simultaneous congruences of integers should also give the extended form (as well as note the adjustments that must be made in finding the solution) in which some textbooks present the Chinese remainder theorem:

a_i x \equiv b_i \pmod{n_i} \quad\mathrm{for}\; i = 1, \cdots, k.

rather than only

x \equiv a_i \pmod{n_i} \quad\mathrm{for}\; i = 1, \cdots, k.

which is what currently appears on the page. I'm not saying to replace the simpler form with the more generalized form, but rather that both should be mentioned. And it might be a good idea to rewrite the simpler form as

x \equiv b_i \pmod{n_i} \quad\mathrm{for}\; i = 1, \cdots, k.

so that there is no confusion about a switch of variables with the extended form.

—Lowellian (reply) 04:38, 30 September 2005 (UTC)

[edit] Minor Point

If I may, the example given of x = {2,3,2} (mod{3,4,5}) doesn't require the Chinese Remainder Theorem. It implies that x-2 = {0,1,0} (mod{3,4,5}), which is equivalent to x-2 = {1,0} (mod{4,15}), which can be done with the plain old Extended Euclidean Algorithm. I'd recommend changing that last 2 to a 0, or adding another modulus, or both. Black Carrot 18:26, 28 July 2006 (UTC)

Be bold! Dmharvey 18:35, 28 July 2006 (UTC)
Will do. Black Carrot 05:05, 30 July 2006 (UTC)

[edit] What step am I missing in example?

"For example, consider the problem of finding an integer x such that

   x \equiv 2 \pmod{3}, \,\!
   x \equiv 3 \pmod{4}, \,\!
   x \equiv 1 \pmod{5}. \,\!

Using the extended Euclidean algorithm for 3 and 4×5 = 20, we find (−13) × 3 + 2 × 20 = 1,"

Nope! I get ( 7) x 3 + (-1) x 20 and so do all the Euclidean algorithm demonstration programs I hunted down. 68.252.105.84 04:41, 13 August 2006 (UTC)

What constraint is unstated and key to the determination?

"i.e. e1 = 40." ??????What constraint is unstated and key to the determination?

Using the Euclidean algorithm for 4 and 3×5 = 15, we get (−11) × 4 + 3 × 15 = 1. Hence, e2 = 45.

Same difficulty.

'Further study shows that my calculations produce a solution congruent with the author's. I still do not understand how the author calculated his extended euclidean algorithm to obtain the intermediate e1, e2, e3 shown'

Retrieved from "http://en.wikipedia.org../../../c/h/i/Talk%7EChinese_remainder_theorem_2bca.html"