Talk:Chinese remainder theorem

Algebraic method

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

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?

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

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 ≡ 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)

Inconsistent scope of generalizations

In the introductory text, it says that CRT has been generalized to commutative rings with a formulation involving ideals. After reading this sentence, I thought there will be an entry about generalization to arbitrary commutative rings. But instead, there is only one entry about generalization to arbitrary (not necessarily commutative) rings. — Preceding unsigned comment added by Vincent B. Hwang (talk • contribs) 05:37, 14 December 2021 (UTC)

 Fixed However, the commutative case is much more used that the non-commutative one, and this may explain this discrepancy. D.Lazard (talk) 11:26, 14 December 2021 (UTC)