Talk:Chinese remainder theorem

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)

23 in Example

I have a very silly question. I can not for the life of me see where 23 comes from and how it is calculated in the example given. This should be clear in an article like this for an uninitiated reader like me. Am I missing something obvious? 143.104.10.0 (talk) 14:10, 16 August 2024 (UTC)

You are talking about the lede, right? 23 would be the value that the Chinese Remainder Theorem guarantees exists. At that point in the article, you have not seen the computations, so it is no wonder that you don't see how it is obtained. You should just verify that it satisfies the conditions (that 23 has remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7). How one obtains 23 (where it "comes from and how it is calculated") is precisely the content of the Chinese Remainder Theorem proof/computation. The lede is not the place to explain how to solve the problem, it only shows you what the result would state. Magidin (talk) 16:08, 16 August 2024 (UTC)

Thank you, but still something here does not make sense: “without knowing the value of n, we can determine that the remainder of n divided by 105 (the product of 3, 5, and 7) is 23. Importantly, this tells us that if n is a natural number less than 105, then 23 is the only possible value of n”. 23 seems to appear magically or the sentence needs to reconstructed. We don’t know n, but then we know it is 23. 72.69.210.72 (talk) 02:26, 17 August 2024 (UTC)

I think some more explanation is needed there. Bubba73 ^{You talkin' to me?} 04:16, 17 August 2024 (UTC)