Talk:Chinese remainder theorem

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)

$x=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}$

Please correct me if mistaken. My understanding is that solving the Chinese Remainder of a list of (remainder, divisor) pairs, where all the divisors are pairwise co-prime, should result in a non-negative integer less than the product of the divisors.

Using the formula $x=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}$ under Case of two moduli, however, $x$ could be negative. For example, consider

${\begin{aligned}x&\equiv 8{\pmod {15}}\\x&\equiv 2{\pmod {7}}\end{aligned}}$

We get $m_{1}=1,m_{2}=-2$ by the extended Euclidean algorithm. But

${\begin{aligned}x&=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}\\&=8\cdot -2\cdot 7+2\cdot 1\cdot 15\\&=-82.\end{aligned}}$

It seems therefore the solution $x$ is incomplete without further applying a modulo operation $x$ = mod(x, $n_{1}n_{2}$). In this example, mod($-82,15\cdot 7$)$\,\,=23$. If so, the solution of the system of congruences under Existence (direct construction) would also seem incomplete.