Talk:Chinese remainder theorem

(Rated C-class, High-importance)

This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.

Mathematics rating:

C Class

High Importance

Field:

Number theory

Chinese remainder theorem has been listed as a level-5 vital article in Mathematics. If you can improve it, please do. This article has been rated as C-Class.

More practical approach[edit]

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? — Preceding unsigned comment added by 208.58.249.208 (talk) 21:11, 18 February 2003 (UTC)

Yup, pretty practical that one. Happens to me all the time. AxelBoldt (talk) 05:49, 19 February 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? — Preceding unsigned comment added by 208.58.249.145 (talk) 09:47, 19 February 2003 (UTC)

Mathematicians, of course! —Lowellian (reply) 04:32, 30 September 2005 (UTC)

This flippancy is typical of the crowd that writes mathematics articles on Wikipedia. So long as it remains the de facto response, Wiki-maths articles will remain resources only useful for people who already know their content, and society at large will continue to miss out on an excellent opportunity for interested parties to learn about mathematical concepts. But at least no one will ever be obliged to write an article with more examples than sigmas and maps, and mathematics will remain the sacred domain of the mystifyingly abstract... Honestly, how does this attitude fit with the project of creating a general encyclopedia? JSoules (talk) 21:43, 22 June 2008 (UTC)

Fully agree: at least some common explanation on how this is used in real life would be welcome for the non mathematicians. The article has been referenced to when the Electronic Patient Filing system in the Netherlands got compromised. [[1]] but why it got compromised because of the use of this theorem stays unclear to a lot of people. Maybe someone can enlight the non math minded. —Preceding unsigned comment added by 87.111.36.238 (talk) 19:23, 1 April 2009 (UTC)

There is a practical application for this theorem - resolution of ambiguity in pulsed radar systems. If the first pulse is transmitted and the reflected return is not recieved before the next pulse, it is said to be ambiguous. Typically a stream of pulses is transmitted with known, fixed pulse repitition interval (PRI) and the target data is integrated to allow small targets to be detected within noise. The range measurement (based on the time since last transmission) is an input to the ambiguity resolution alogorithm. Another PRI is then used, giving a second range ambiguous measurement. Typically in a practical system 3 carefully chosen PRIs will be sufficient to resolve ambiguities out to the "instrumented range" which is one of the defining parameters of the transmitted waveform design. Thus we have three PRI derived range ambiguity values and three ambiguous measurements from which to determine the unambiguous range. —Preceding unsigned comment added by 20.133.0.13 (talk) 14:42, 20 October 2009 (UTC)

Thank you, User:20.133.0.13. That sounds like a relevant application, so I added a brief mention of radar range ambiguity resolution, as you mentioned, to the article.--DavidCary (talk) 21:19, 29 November 2015 (UTC)

Re: Finding the solution with basic algebra and modular arithmetic[edit]

Can someone please explain and clarify this statement in the article?:

... hence 3 × t = 1 (mod 4), or t = (1/3) (mod 4) = 3 (mod 4) ...

I don't agree with this. How is it the case that (1/3) (mod 4) = 3 (mod 4)? --Wykypydya (talk) 08:09, 20 October 2012 (UTC)

As I said in my edit summary, this is basic and standard modular arithmetic.

1 (mod 4) = 3 x 3 (mod 4)

then divide both sides by 3:

1/3 (mod 4) = (3 x 3)/3 (mod 4) = 3 (mod 4)

—David Eppstein (talk) 19:04, 20 October 2012 (UTC)

But in order to have equivalence under mod n, aren't you supposed to be able to add or subtract a multiple of n to get to every number in the equivalence class? You can't add any integer multiple of 4 to 1/3 to get 3; any multiple of 4 that is added to 1/3 will not be an integer. Am I missing something? Thanks, --Wykypydya (talk) 19:39, 20 October 2012 (UTC)

You are thinking of 1/3 as being a real number somewhere between 0 and 1. In modular arithmetic, this is mistaken and wrong. 1/3 means, simply, the number that when multiplied by 3 gives 1. And, modulo 4, this number is 3. See modular multiplicative inverse. —David Eppstein (talk) 20:03, 20 October 2012 (UTC)

You're missing his point. 1 mod 4 = 1. 3 mod 4 = 3. Thus, it should be (1 mod 4) * 3 = 3 mod 4. Then everything would make sense, because dividing both sides by 3 gives 1 mod 4 = 1 mod 4. -- — Preceding unsigned comment added by VastNova (talk • contribs) 18:08, 23 July 2016 (UTC)

SIMPLY PUT

3 is congruent (==) to 1 mod n (not equal, congruent)

means 3*x = n*y + 1 (only integer solutions wished) or Mod[3*x,n]=1

it can be called a diophantine equation can be solved by inversemod

if a==b mod m and c==d mod m, a+c==b+d mod m, which explains only how a+c can be added across the same m if one only needs to be congruent to (ie, not same x or y but same after x and y are found).

as all the rules of modular arithmetic residues and ring theory when backsubstituting across different moduli and all the rules one might incurr: i'm asking the same thing. — Preceding unsigned comment added by 72.219.207.160 (talk) 22:57, 14 December 2013 (UTC)

Proof of Dedekind's theorem[edit]

~~What does big $K$ refer to? It appears from nowhere.--李4 (talk) 23:56, 29 October 2015 (UTC)~~ Now the question becomes: is the product really equal to the intersecting, considering that a monoid is not necessarily commutative.--李4 (talk) 23:58, 29 October 2015 (UTC)

A not too technical example[edit]

I completely agree that these math articles have become nearly useless for non-mathematicians. I have written a "Not too technical example" section which I will add to the article in a few days, pending any discussions here. It follows:

A not too technical example

Consider 7 x 11 x 13 = 1001

By the Chinese Remainder Theorem we can represent any number N between 1 and 1001 with three smaller numbers, namely: Na = N (mod 7), Nb = N (mod 11) and Nc = N (mod 13). And this representation in terms of these three remainders is unique.

Therefore a second number M, must produce a different set of three remainders: Ma = M (mod 7), Mb = M (mod 11) and Mc = M (mod 13)

Now the usefulness of the CRT comes when we want to exactly add or multiply integers represented in this way. For example the sum S of N and M and the product P of N and M are each represented by a triple of numbers (Sa, Sb, Sc) and (Pa, Pb and Pc) and it turns out that:

Sa = Na + Ma (mod 7), Sb = Nb + Mb (mod 11) and Sc = Nc + Mc (mod 13) and Pa = Na * Ma (mod 7), Pb = Nb * Mb (mod 11) and Pc = Nc * Mc (mod 13)

For example let's take N = 26 and M = 100. Then Na = 5, Nb = 4 and Nc = 0; Ma = 2, Mb = 1 and Mc = 9.

Now Sa = 5 + 2 = 0 (mod 7), Sb = 4 + 1 = 5 (mod 11) and Sc = 0 + 9 = 9 (mod 13) but (0, 5, 9) are the representation of N + M = 126, because 126 mod 7 is 0, 126 mod 11 is 5 and 126 mod 13 is 9.

And similarly Pa = 5 * 2 = 3 (mod 7), Pb = 4 * 1 = 4 (mod 11) and Pc = 0 * 9 = 0 (mod 13) while the representation of N * M = 2600 is indeed (3, 4, 0).

What we've accomplished is that addition or multiplication of two "large" numbers (26 and 100) have in both cases been replaced with three additions or multiplications of two much smaller numbers. Now numbers less than 1001 are not very "large" but this is just an example. In use, numbers much larger than the size of a computer word can be exactly added, subtracted and multiplied (but not divided) by using more than the three bases (7, 11, 13) of our example and by choosing those bases much larger. They only have to be relatively prime to each other in pairs.

Furthermore, although our example represents the numbers from 1 to 1001, in fact any consecutive sequence of 1001 integers can be represented by these three bases (7, 11, 13): the sequence needn't start at 1.

End of example --RobLandau (talk) 15:50, 10 July 2016 (UTC)

It is not a good idea to put a new post in the middle of a discussion, which is several years old. Therefore I have moved it in its right place, which is a new section at the bottom of the page.

I agree that this article is too technical for most users. In particular, the lead does not satisfies Wikipedia standards. It should contain, among other lacking things, a description of the usefulness of the algorithm (this is done in your draft, but this would be better placed in the lead). I'll try to rewrite the lead in the next days. Then we could discuss where to place an example and how to write it. D.Lazard (talk) 16:23, 10 July 2016 (UTC)

I have rewritten the beginning of the article in a way that I find less technical and easier to understand. I have also reorganized the section for making more visible the section containing a simple example. After these edits, I am able to discuss your draft. IMO, it is not an example of the Chinese remainder theorem, but an example of one of its main application, "multi-modular computation". This deserve a section in this article, which is presently lacking. IMO, such a section must separate the definition of the concept, a simple example of it, and its application to linear algebra. Your draft may be useful for the example subsection, but some work is needed for better distinguishing between the theory and the example, and for putting it in a more encyclopedic style (see MOS:MATH and WP:MOS). D.Lazard (talk) 10:00, 13 July 2016 (UTC)

A section on "multi-modular computation" would be fine. BUT the *main* problem that the "NTT example" above was intended to minimize is that most intelligent non-mathematicians might not get past the third section of the main article: the formalism and notation might create a forest where every tree has a horizontal branch 1 meter off the ground through which they would need to ride. The order of sections I favor would be a lead, a history, an NTT example, then the theorem statement and proofs, then applications. But if an NTT example doesn't come near the beginning, it won't be useful-- involved mathematicians would not need it, and if buried in the article, non-mathematicians would have turned away before finding it. Also I would be careful about putting it in a more encyclopedic style -- if that means making it more pedantic or less smoothly flowing (I think it's a bit ragged as it is). RobLandau (talk) 12:58, 13 July 2016 (UTC)

In principle, I agree with you. However, in this particular case, a NTT example is not so easy to design. Your draft is not convenient for this, as you have to explain some more technical things, like the fact that CRT gives a other representation of numbers in some interval, and that this representation is compatible with the arithmetic operations. Maybe, this example section could be about the simplest case (modulo 6 vs. modulo 2 and 3) with a complete table of the correspondence. With this table, it is easy to show that this is not only a bijection, but also that it preserves arithmetic operations, and is thus a ring isomorphism. Such a simple example would also allows us to explain the relationship between the different statements of the CRT. D.Lazard (talk) 13:20, 13 July 2016 (UTC)

Could you produce such a simple table as you mention above? It would clarify for me what you have in mind. As to your "you have to explain some more technical things, like the fact that CRT gives a other representation of numbers in some interval, and that this representation is compatible with the arithmetic operations" it seems to me (unless I misunderstand you) that this is exactly what my example does--but by example, not by explanation and without needing to use the term "ring isomorphism" that would need looking up by those readers I am concocting my example for. It might not hurt the article to have two examples, perhaps in different places, one that satisfies your needs and one like the NTT above. RobLandau (talk) 16:56, 15 July 2016 (UTC)

How about a table like this, showing that the integers between 1 and 12 fit neatly into a 3x4 grid of remainders? To me this makes the CRT result more plausible, and the table is big enough to show the diagonal pattern made by the increasing integers.

		0	1	2	3
		Remainder when divided by 4
By 3	0	12	9	6	3
	1	4	1	10	7
	2	8	5	2	11

-- John of Reading (talk) 07:21, 22 July 2016 (UTC)

Thanks. Nevertheless, the accompanying text is still to be written. D.Lazard (talk) 08:17, 22 July 2016 (UTC)

Applications[edit]

I have almost finish to clean the article up. It remains

to write the introducing simple example (see preceding thread)
to move the proof using partial fraction decomposition from § Hermite interpolation to the top of § Over univariate polynomial rings and Euclidean domains, and to update the subsections. Done
to add a section about multi-modular computation
to cleanup the section "Applications"

I have a problem with this section. In fact, it consists in saying "Here is a list of results using CRT". This list is far to be complete, and the chosen examples cannot be understood without knowledge in various area of mathematics. Thus either a reader already knows the area of mathematics involved by one of the examples, and the text accompanying this example is not useful for him, or he does know this area, and the example means nothing for him. Therefore, I suggest to remove this section, or to replace it by a bulleted list of links to articles using CRT. Some opinion?

The subsection § Dedekind's theorem sets a different problem, as there is, apparently, no article to be linked, and there is no evidence that CRT is fundamental for the proof. Moreover, the version of CRT which is involved is the generalization to arbitrary rings, which is generally not referred to under the name of Chinese remainder theorem. Therefore, this section must be moved elsewhere. Where? I'll ask the question to Wikipedia talk:WikiProject Mathematics‎ § A Dedekind's theorem D.Lazard (talk) 08:54, 22 July 2016 (UTC)

Finding the Solution: Exhaustive Search is worded confusingly[edit]

4 + 5 = 9 mod 4 →1

This crams a couple of separate steps into one. While the apt reader will understand, it's just as easy to convert it to something like: 4 + 5 = 9 and 9 mod 4 →1

Thoughts? --VastNova (talk) 18:15, 23 July 2016 (UTC)

Algebraic method[edit]

Fly by Night has recently added a section § Algebraic method to the article. I have reverted it with the edit summary "Unsourced, and the general description of the method is lacking". Fly by Night has reinstalled this section (with a reference added) after qualifying (on my talk page) my revert of unfair. By this he violates both WP:NPA and WP:BRD rules: WP:BRD states clearly that, when an edit is reverted, one should not revert the revert. Instead, one has to discuss on the talk page for searching for a consensus. Therefore, I will revert again Fly by Night's edit. Please do not reinsert it without discussing the content here, and raising the following points.

Heading: This method is no more algebraic than the others given in the other sections. Thus qualifying it of "algebraic" is confusing for the layman, and must be avoided.
Heading again: Although the heading contains "method", I do not see any method in the section, only ad hoc computation on a specific example.
Content: As a professional mathematician, I am unable to understand the method behind this computation.Thus, there is not hope that a normal reader can use it for running another example.
Content: It seems that the method consists in applying the method Linear system § Eliminations of variables, but without citing it and without saying how it has to be modified for dealing with the fact that one want only integer solutions. This has to be clarified before reinstalling this section.

D.Lazard (talk) 16:07, 31 August 2016 (UTC)

@D.Lazard: When I describe your edit as unfair, I did not say anything about you personally, so I really can't see how I have made a personal attack. I'm also flabbergasted by your reference to WP:BRD given that you reverted without discussion. I was the one to initiate contact! In reference to your objections: If you don't like the heading then change it. If you don't like the title "algebraic" then suggest a better one. If you think I've applied a method without naming it then name it. Yes, the method referes to a specific example, but so too do the other two. Please, sit down and work through another example - the method is sound. This is a public encyclopedia and we should help one another create better content. The main way to do that is to make improvements that you think necessary. I've looked through your edit history and you often make wholesale deletion of content that you disagree with. This is not fair. I am trying to improve this encyclopedia. Why not work with me and make changes to my edit to improve it? — Fly by Night (talk) 19:20, 1 September 2016 (UTC)

@Fly by Night: My reading of WP:BRD would be that it does not apply to the first revert, but rather to trying to restore changes that have been reverted. As to the addition, I would say it needs heavy improvement. It needs a brief introduction and explanation, it needs the proper referencing (this is a variant of "back substitution" or elimination of variables, as noted), it needs a better title (no more or less algebraic than other sections). It could also benefit from comparisons to the other methods (it tends to work better and faster than the constructive proof when the moduli are small, for example). Given that it requires extensive improvement before it is ready, I think D.Lazard used the cycle described in WP:BRD correctly; at this point, it should be discussed in the talk page so that it can be whipped into shape before being re-added. Just saying "If you think this is not good enough, then fix it!" is to try to shift the responsibility for making a suitable addition where it shouldn't be in the first place. Magidin (talk) 22:12, 1 September 2016 (UTC)

I share none of D.Lazard's objections. I have other somewhat related concerns with the article, however: the entire "finding the solution" section is not very well written, nor cited. The first two methods are essentially the same, as are the latter two methods. The first two methods are absurd as a practical matter. The latter two methods are not absurd, but they are redundant with the second proof of existence. Some trimming and rearranging is definitely in order. --JBL (talk) 22:16, 1 September 2016 (UTC)

If I were to give a completely accurate (but unsourceable) name to this method, it would "intersection of cosets by substitution and modular arithmetic". Each congruence

x\equiv t{\bmod {m}}

defines a coset of the subgroup mZ, and any technique for solving simultaneous congruences can be interpreted as a method for intersecting these cosets. The content of the method under discussion appears to be that two cosets can be intersected by substituting a generator for one into the equation defining the other, and then modular arithmetic allows one to solve for an additional condition on the generator.

I have one other comment. Suppose one wishes to solve a congruence modulo

m_{1},\ldots ,m_{k}

. The so-called "brute force approach" requires computing

\textstyle \sum _{i}\prod _{j\neq i}m_{j}=(\prod _{j}m_{j})(\sum _{i}m_{i}^{-1})

values. If all moduli are roughly equal to some constant M, then this is roughly

kM^{k-1}

operations. The "exhaustive search" requires at most

\textstyle \sum _{i}\prod _{j>i}m_{j}

values. This is roughly

M^{k-1}+M^{k-2}+\cdots +M

operations. When written in O-notation, the difference between these two gets swallowed up and they are both

O(M^{k-1})

. Nevertheless, since the main interest in these methods is hand computation, I think the article is wrong to say that this method is "essentially the same method" as the "brute force approach". The constant matters a great deal when you are doing arithmetic by hand. (Of course, if one is comfortable computing modular inverses by hand, then the other methods are faster still.) Ozob (talk) 00:20, 2 September 2016 (UTC)

@Ozob, Joel B. Lewis, and Magidin: Do you think the content should be included - perhaps subject to some revision? — Fly by Night (talk) 18:23, 2 September 2016 (UTC)

I think the content should not be included unless extensively revised. So I support its initial revert. Magidin (talk) 18:30, 2 September 2016 (UTC)

@Magidin: Could you please suggest the revisions? The content that I added was an adaptation of a method from a well-known textbook for first year undergraduates. — Fly by Night (talk) 20:27, 2 September 2016 (UTC)

I am familiar with the method; I teach it in class. And I already suggested what I think it needs, in broad strokes: "It needs a brief introduction and explanation, it needs the proper referencing (this is a variant of "back substitution" or elimination of variables, as noted), it needs a better title (no more or less algebraic than other sections). It could also benefit from comparisons to the other methods (it tends to work better and faster than the constructive proof when the moduli are small, for example)." If your question was meant instead to be, "Could you please do the work of improving it for me?" then, no. Magidin (talk) 20:45, 2 September 2016 (UTC)

@Magidin:My question was not "Could you please do the work of improving it for me?" That's why I asked you to suggest revisions. Having said that, let's try to remember that this is a cooperative project where we should help one another. Please don't take this the wrong way; try to see it from my point of view: I made a good faith edit which was referenced and which you teach to your own classes but it was simply deleted. There is no way for me to proceed. Someone doesn't like an edit so they delete it. People say that improvements need to be made, but won't help to make them. We find ourselves in a situation where a well-known method that is taught around the world cannot be added to the article because one person doesn't like what was written. — Fly by Night (talk) 22:55, 2 September 2016 (UTC)

I believe that this section of the article (not just this particular method) needs wholesale revision. There should be clear statements of the algorithms being proposed; it doesn't have to be overly formal, and I would like to keep the examples, but there should be something more general for someone who doesn't yet grasp the underlying principles. Ozob (talk) 23:52, 2 September 2016 (UTC)

@Ozob: I agree. But how do I go about making such revisions/additions when they are immediately deleted? — Fly by Night (talk) 01:32, 3 September 2016 (UTC)

@Fly by Night: You are asking me to make the revisions. Whether you characterize them as "suggestions" or not, you are asking that I do the work of rewriting your material so that it can be added. I think this needs too much revision, and too much effort, that I simply cannot spare the time to do right now (reviewing a proposed addition or making minor changes to it, by contrast, would not take as much time). As part of my cooperation in this, I indicated the type of change and content that I believe the portion would require. You claim this makes it impossible for you to proceed; but that simply means that you are unwilling or unable to engage with the suggestions made ("add an explanation", "add an introduction", "compare it to the other methods"). That is help; when I referee a paper, I don't rewrite it for the author: I tell the author what kind of changes should be made, and let the author attempt them, for example; that does not mean I'm not helping. Your characterization of the situation is also rather disingenuous: I do not know if it is a "well-known method taught around the world" (do you have any evidence for this? I am only aware of it being taught in two countries, and not universally in either; and the method is not known to many people I know). It wasn't just one person who didn't like what was written (I also find the way it was proposed to be insufficient and in need of too much rewriting to warrant inclusion until that is done, for one). It is also patently false that "it cannot be added"; it just should not be added written in the manner in which you attempted to add it. Perhaps cutting down on the hyperbole would help. If you find this frustrating, well, I find your reaction to be frustrating as well. At this point, what I would try to do with an addition is to read the criticisms and suggestions presented, and attempt to incorporate them into a write-up that I would put up in the talk page as a suggestion for addition. If you cannot or will not do that, well, then you'll have to wait until I or other people have the time and inclination to do it for you.Magidin (talk) 01:01, 3 September 2016 (UTC)

@Magidin: I'm probably being foolish, but where are the hyperbolae in my addition. (Please read it) — Fly by Night (talk) 01:32, 3 September 2016 (UTC)

@Fly by Night: The hyperbole are in your comments. "There is no way to proceed" (yes, there is); "well-known method taught around the world" (at best an unwarranted pair of assertions); "cannot be added because one person doesn't like it" (no, it wasn't just one person, and there was more expressed than a simple personal dislike). As to how do you go about making the corrections/additions: you make the proposals in the talk page; they will not be "immediately deleted" in the talk page. That's how consensus is built. Oh, and by the way, thanks for the insinuation that I am commenting without having read your addition in the first place. For the record, I read it before I first commented, so thanks for the vote of confidence in my integrity and honesty. Magidin (talk) 03:17, 3 September 2016 (UTC)

Finding the solution[edit]

It has been said in the preceding section that the whole section § Finding the solution needs a revision. I agree, and will begin to do it, along the following line:

renaming the section "Computation"
expanding the general introduction of the section by adding to the example the general specification of the computation problem
replacing the content of section "Brute-force approach" by the first method of next subsection (IMO, this brute-force approach has been imagined by a set-theorist who has never computed anything; it is difficult to imagine a method which is together so inefficient and so complicate)
adding indication on the complexity of the different methods
expanding the section "using the existence construction"
adding a section "As a linear Diophantine system": all methods for linear Diophantine systems may be used here, and Fly by Night's one is only one of them.

D.Lazard (talk) 16:59, 3 September 2016 (UTC)

Thank you! I look forward to it. Ozob (talk) 18:53, 3 September 2016 (UTC)

Indeed, thank you; I wish I had the time. I'll pitch in as time permits. Magidin (talk) 20:24, 3 September 2016 (UTC)

I have completed above edit program. Feel free for improving the result. In particular, references to The Art of Computer Programming should be added and used for improving details (I have not this book under hands, and some details of my edits are based on what I remember of my readings). D.Lazard (talk) 10:09, 9 September 2016 (UTC)

The mission of Wikipedia is that it be an encyclopedia, but Wikipedia is infamous for being incomprehensible to non-experts. The section on simultaneous Diophantine equations gives no method, and the links are not very helpful. I think that an explicit example, like the one I originally added, would be a good idea. If we want people with basic mathematical literacy to get something from the article then I think we need the example I gave. I'm sorry, but all of the links given in the section would be totally incomprehensible for someone that doesn't already understand the topic at a higher level. — Fly by Night (talk) 19:29, 9 September 2016 (UTC)

I think the link to Diophantine_equation#System_of_linear_Diophantine_equations is quite helpful. That section of that article gives a precise description of the algorithm, and, despite your objection, I don't think it would be "totally incomprehensible". True, it doesn't provide an example, and neither does the new section of this article; but it's a good exercise to apply the general algorithm to a special case. If you think this section of the present article would benefit from continuing the running example, I suggest you add it. Ozob (talk) 18:49, 10 September 2016 (UTC)

It is not incomprehensible to someone that already understands the topic - that was my point. But for a casual reader or the majority first year undergraduates, the links are incomprehensible. Heck, I understand the topic and yet find the link baffling. Remember that not everyone is blessed with tremendous mathematical intelligence. With regards to adding an example: I tried that once before and got my fingers burned. Id rather not spend time adding something that will get reverted. — Fly by Night (talk) 00:22, 11 September 2016 (UTC)

Is the coprime condition necessary and sufficient for the ring isomorphism?[edit]

In the section 'Theorem statement', the article states "if the $n_{i}$ are pairwise coprime" then we have the ring isomorphism $\mathbb {Z} /N\mathbb {Z} \cong \mathbb {Z} /n_{1}\mathbb {Z} \times \cdots \times \mathbb {Z} /n_{k}\mathbb {Z}$ . I know from my group theory course that the $n_{i}$ are coprime *if and only if* we have the *group* isomorphism. If this is also true for the ring isomorphism then I suggest it be added to the article. Similarly in the section 'Generalization to arbitrary rings', the article states "If the ideals are pairwise coprime, we have the isomorphism", and if this is necessary and sufficient as well then it should be included in the article. — Preceding unsigned comment added by Joel Brennan (talk • contribs) 15:57, 25 April 2019 (UTC)

Uniqueness[edit]

CLAIM: Suppose that x and y are both solutions to all the congruences. As x and y give the same remainder, when divided by ni, their difference x − y is a multiple of each ni. As the ni are pairwise coprime, their product N also divides x − y

given N > 1
given x,y < N
then -N < x-y < N

if x>y, 0 < x-y < N
and 0 < (x-y) / N < 1
so N does not "divide" (x-y)

if x<y, -N < x-y < 0
and -1 < (x-y) / N < 0
so N does not "divide" (x-y)

if x=y, x-y = 0
and (x-y) / N = 0
so only in this case does N does "divide" (x-y)

it is better to simply say x is equivalent to y modulo N, x ≡ y (mod N) — Preceding unsigned comment added by Nonki72 (talk • contribs) 21:32, 19 April 2020 (UTC)

The first part of the uniqueness proof is to show that

x \equiv y (mod N)

. This part of the proof does not require that

x, y < N

as you have assumed. The second part is to show that there is only one solution that is non-negative and less than

N

. It is this that you have provided a correct proof for. The article just indicates that this is so without providing the details. The argument is simple and so there is justification for omitting it. As Wikipedia is an encyclopedia and not a math text (see WP:NOTTEXTBOOK) most proof details are not included.--Bill Cherowitzo (talk) 22:45, 19 April 2020 (UTC)

anhducwiki

Thursday, September 10, 2020