Talk:Chinese remainder theorem/Archive 1

Archive 1

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 — Preceding unsigned comment added by Georg Muntingh (talk • contribs) 10:45, 12 January 2002 (UTC)

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 (talk) 12:40, 12 January 2002 (UTC)

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 — Preceding unsigned comment added by Matthew Woodcraft (talk • contribs) 09:04, 12 January 2002 (UTC)

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 — Preceding unsigned comment added by AxelBoldt (talk • contribs) 04:35, 14 January 2002 (UTC)

This is a lot better than my writings. --Georg Muntingh — Preceding unsigned comment added by 129.125.21.xxx (talk) 09:46, 14 January 2002 (UTC)

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)

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. — Preceding unsigned comment added by 68.252.105.84 (talk) 04:41, 13 August 2006 (UTC)

'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' — Preceding unsigned comment added by 68.252.105.84 (talk) 19:09, 14 August 2006 (UTC)

The most common form should be described

The CRT is used extensively in two-prime RSA.

It is almost always implemented using the equation (assuming p > q): M = (((Mq - Mp) * ((1/p) mod q)) mod q) * p + Mp.

This is a special case of "Garner's Algorithm." — Preceding unsigned comment added by 67.119.74.222 (talk) 19:46, 22 May 2007 (UTC)

The general Hermite interpolation problem and the Chinese remainder theorem

It seems interesting to add some remarks about the connections with the classical Hermite interpolation problem (in the general form: find a polynomial with prescribed derivatives up to a certain order in some prescribed nodes). I've done it in the section "Applications"; it could then be expanded or moved elsewhere indeed (apparently there is no article on the general Hermite interpolation yet). --PMajer (talk) 21:44, 28 December 2008 (UTC)

3 Suggestions

It seems like a nice article. Here are 3 suggestions.

1) After the numerical example add something like the following. Note that the sum of the ei is equivalent to 1 mod the product of the ni. This can save one application of the Euclidean Algorithm. In the example, 1-(e1+e2) = -84 and this can be used for e3 (or, reduced mod 60 to -24).

2) ("Non-commutative case") The first sentence is somewhat confusing since the second paragraph "On the other hand..." seems to give a generalization. Perhaps you can insert "in the above form" in that first sentence. You might want to refer to Hungerford "Algebra" for the non-commutative version (he gives a statement for certain such rings not necessarily having an identity.)

3)("Non-commutative case"--at end). Consider the following slight variant. Let Ji be the product of the Is, s not = i. By induction R = J1+J2+...+Jn. Your argument proves: Intersection(Ii) = I1J1+I2J2+...+InJn.

````G. Blaine —Preceding unsigned comment added by G. Blaine (talk • contribs) 20:35, 13 March 2009 (UTC)

-Let me add that I don't think you should have to go to a separate page ("Extended Euclid Algorithm") in order to understand this article. The Chinese made the Chinese Remainder Theorem without referencing Euclid. If it is an integral part of the Chinese Remainder Theorem, it should be included in brief here, and done out numerically in at least one of the examples. Keep in mind that many of the people who look at this article will be students who want to be shown an explicit procedure, so they can apply it to their homework problems. Clarity is more important than compactness. —Preceding unsigned comment added by 82.136.242.43 (talk) 03:40, 18 March 2010 (UTC)

More applications

I see here [1] a nice list of applications with good references. These may possibly provide nice hints for the section "Applications" of this article.--pma 10:19, 30 July 2010 (UTC)

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 — Preceding unsigned comment added by AxelBoldt (talk • contribs) 00:04, 12 January 2002 (UTC)

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 — Preceding unsigned comment added by AxelBoldt (talk • contribs) 03:24, 12 January 2002 (UTC)

The ideals (X) and (Y) are not coprime (i.e., (X)+(Y) does not equal the ring F[X,Y]), which is why the CRT doesn't hold for (X) and (Y). See page 131 of Thomas Hungerford's "Algebra" text for a generalized theorem over rings. Jannaston (talk) 19:04, 1 November 2010 (UTC)

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)

I'd suggest appealing to the Linear congruence theorem which lets you transform congruences of the "extended" form into the "simple" form, when possible. Quantris (talk) 18:30, 18 July 2011 (UTC)

Moduli that aren't coprime

Anyone feel up to adding a constructive solution for moduli that aren't necessarily coprime? The following probably needs some work to make it clearer.

It works in a similar way to what is already present, but is simpler to explain assuming there are only two congruences:

${\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}}\\\end{aligned}}$

Let $g=\gcd(n_{1},n_{2})$; then $a_{1}\equiv x\equiv a_{2}{\pmod {g}}\Rightarrow a_{1}\equiv a_{2}{\pmod {g}}\quad$ is a necessary condition.

Then we may write $a_{i}=k_{i}g+r\quad \mathrm {for} \;i=1,2$ (with 0 ≤ r < g). Also, by the Extended Euclidean algorithm, we can find p and q such that $g=pn_{1}+qn_{2}$. Then, $x_{0}=k_{2}pn_{1}+k_{1}qn_{2}+r$ satisfies the original congruences, as does any multiple of $\mathrm {lcm} (n_{1},n_{2})=(n_{1}n_{2})/g$ added to x<sub>0</sub>. In other words, we've combined the original congruences into the equivalent:

$x\equiv k_{2}pn_{1}+k_{1}qn_{2}+r{\pmod {\mathrm {lcm} (n_{1},n_{2})}}$

You can check that this is the same result as what is already in the article for the case when the moduli are in fact coprime (g is 1). Further, it is easy to see how to extend this construction to more than two congruences; simply combine them two at a time until there are none left. Quantris (talk) 18:59, 18 July 2011 (UTC)

Simpler intro ?

The lead section goes straight into mathematical jargon. Is it possible to write something that non-mathmos might have a chance of understanding ? - there's a practical example on Simple English Wikipedia which could be used. Pat. 81.159.182.3 (talk) 19:37, 22 July 2011 (UTC)

On the subject of the intro, would it not be a good idea to include the answer to the example (i.e. "For example what is the single lowest number if repeatedly divided by 3 gives a remainder of 2; when divided by 5 gives a remainder of 3; and when divided by 7 gives a remainder of 2?") somewhere in the article? It's 23, right? A Thousand Doors (talk | contribs) 02:15, 29 December 2011 (UTC)

Miscellaneous errors

I would just like to point out that there are quite a few typos, and errors in the equations and text of the "Finding the solution with basic algebra and modular arithmetic" Section. I've never edited on wikipedia before, so I will leave that to someone more knowledgeable, but I did want to draw attention to this.

Thanks! — Preceding unsigned comment added by 199.84.62.180 (talk) 02:21, 11 February 2012 (UTC)

External links suggestions

An applet for solving a linear system of congruences by applying the Chinese Remainder Theorem. http://users.otenet.gr/~bpapa/chineseremaindertheorem.htm — Preceding unsigned comment added by 85.73.175.31 (talk) 16:59, 25 May 2012 (UTC)

Confusion Regarding Bezout

"Since $\scriptstyle \gcd(n_{1},n_{2})\,=\,1$, we have from Bézout's identity

$n_{2}[n_{2}^{-1}]_{n_{1}}+n_{1}[n_{1}^{-1}]_{n_{2}}=1.$"

should this be = 1 (mod N) ?

e.g. $ifn_{1}=2andn_{2}=3=>n_{2}[n_{2}^{-1}]_{n_{1}}+n_{1}[n_{1}^{-1}]_{n_{2}}=3[1]_{2}+2[2]_{3}=7\equiv 1\mod {6}$

e.g. $ifn_{1}=3andn_{2}=5=>n_{2}[n_{2}^{-1}]_{n_{1}}+n_{1}[n_{1}^{-1}]_{n_{2}}=5[2]_{3}+3[2]_{5}=16\equiv 1\mod {15}$ — Preceding unsigned comment added by 95.146.129.50 (talk) 20:22, 2 August 2012 (UTC)

• I found that confusing as well. If one normalizes the $[a^{-1}]_{b}$ to be between 0 and (b-1), the sum will consist of two nonzero positive integer products and never be 1. What is meant is that $[a^{-1}]_{b}]$ should be the exact inverse calculated by the extended euclidian algorithm, then (and only then) it will be exactly 1 and not only 1 (mod N). I will edit to clarify. X127 (talk) 04:16, 3 April 2013 (UTC)

If a and b are co-prime, then Bezout's identity essentially guarantees the existence of two numbers x and y such that $ax+by=gcd(a,b)$. The (mod N) is not required. In the example you gave where a = 2 and b = 3, we can have the values of x = -1 and y = 2 such that 3*(-1) + 2*2 = 1. Still another possibility is x = -3 and y = 5, so that 3*(-3) + 2*5 = 1. The values of x and y that can satisfy this identity is not unique. The best way to figure out the values of x and y such that it satisfies this condition is to use the extended Euclidian algorithm.(Manoguru (talk) 16:58, 27 August 2013 (UTC))

Pair at a Time Solution

A problem with the modular arithmitic soln is no obvious algorithm to follow (modular back substitution rules) and possibly not leading to a soln or loosing lcm if not pairwise (complexity).

A problem with "A constructive algorithm to find the solution" (terms of multiples with invmod factor) is pairwise prime restriction and needing to solve "all or none" of m[i]. The algorithm fails if gcd!=1. Mathematica solves this by dividing into lists and some tricky splicing math.

However. Treating the moduli as sawtooth waves all intersecting (easy to graph, all share one y-offset) the soln is their lefts intersect at y==0.

Using that and also including use of GCD for aligning two wave (in obtaining the inverse mod), one can find any CR soln a pair at a time (last, next) without using all the m[i] or the restrictions. Ultimately it becomes a list of terms of multiples like the constructive solution does, excepting gcd is resolved and it works any next m[i] at a time (ie, ability to stop or back up). The current LCM is kept, so only 2 numbers need to be saved to progress.

That sounds slower and is in some cases but in a few is quicker, and is far faster if not congruent (ie, one has data which is not always congruent). But both are "fast".

See link:

• CR solving any two eq at a time, width of CR for all soln — Preceding unsigned comment added by 72.219.207.160 (talk) 20:12, 14 December 2013 (UTC)

Visualization

Where the left (rise) of all sawtooth waves meet on y==0 is a solution, every lcm the wave patterns repeat.

For just two waves that meet at L and R sides, inversemod is the soln.

File:Sawtooth-intersections.jpg

sawtooth intersections, chinese remainders

— Preceding unsigned comment added by 72.219.207.160 (talk) 20:12, 14 December 2013 (UTC)

Existence and uniqueness warning: not uniq

That being said the solution is not unique. If x is a first positive solution after x==0, consider LCM of all m[i] is the max. The length of all waves patterns repeat there is a solution every (LCM). If we consider pairs of m[i] they may have many within the max that satisfy most but not all m[i].

The first soln after x, if it exists, is uniq only assuming that LCM of m[i] is reached prohibiting more soln, that is.

In a system there may be repetition (this is allowed) - that is there was no statement it would not be so - which is also not unique. — Preceding unsigned comment added by 72.219.207.160 (talk) 20:12, 14 December 2013 (UTC)

Bezout not helpful

I don't see the point of multiplying both sides of Bezout's Identity by x and then evaluating the right hand side modulo n1 to conclude that x is congruent to itself modulo n1.

I think you might as well go straight from "we have the multiplicative inverse of each n modulo the other" to

We can now define the value

$x\equiv a_{1}n_{2}[n_{2}^{-1}]_{n_{1}}+a_{2}n_{1}[n_{1}^{-1}]_{n_{2}}$

and it is seen to satisfy both congruences by reducing.

Jmichael ll (talk) 02:29, 27 August 2013 (UTC)

you listed only part of the simple expansion most books list. x=a1*M1*y1+...+ai*Mi*yi mod m where y is inv and Mi is m/mi.

i think the problem is the editor of the page deleted the fuller simpler expression and replaced it with jargon. if i remember it was on the page. — Preceding unsigned comment added by 72.219.207.160 (talk) 23:37, 14 December 2013 (UTC)

Question: modular arithmetic back substitution across differing moduli

where is the pseudocode this? what are all the hidden rules to this flavor of algebra, assuming there are some?

If a==b mod m and c==d mod m, a+c==b+d mod m, which explains only how two eqs can be added across the same m, (noting answer must be taken mod m).

In the example, of just 3 eq, the are many substitutions but only a single modulo 5 reduction after substitution in the 3rd eq which lying in the 1st eq that is mod 3. nothing is said about the result ignoring the mod 3 (ie, if mi,bi must be sorted, which adds non-linear time). or what other special rules apply when trying to implement it

I'd like to see the full pseudocode (which i'd like to see the whole of).

As all the rules of modular arithmetic residues and ring theory when backsubstituting across different moduli and all the rules one might incurr using the method proposed on the wiki page? that easy?

(* see constructive solve, a quick soln *) CR(ai,mi) ; Mi=m/mi ; x = a1*M1*inv_1+...+ai*Mi*inv_i

That is simple add and multiply if one is given inv_i.

I know for inversemod(m2,m1) that if one simply loops i*m2-j*m1==1 over i i'll find i,j - which is a slow soln but easy.

I would like to see recursive pseudo code for the moduli arithmetic method so I can see that when all rules are considered and done it doesn't devolve into a search algorithm (or to great complexity) and is truely a linear time solution, as the "Constructive" method is.

Where even the rough pseudocode for "modular arithmetic backsolving for CR" ? — Preceding unsigned comment added by 72.219.207.160 (talk) 00:17, 15 December 2013 (UTC)

comment on above

I ask that because it's very intersting how it can avoid using inverse mod altogether and use Mod only 2x total. It does require back substitution: however inverse mod required in every term of constructive solution requires this (one per i).

Very interesting it could avoid much work and be so much faster, far simpler, but not be in major math software

But can it be true? Where has it been hiding then ? :)

Let's see the pseudocode. — Preceding unsigned comment added by 72.219.207.160 (talk) 00:25, 15 December 2013 (UTC)

Proof of Dedekind's theorem

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)

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? — 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. [[2]] 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)

A not too technical example

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.

		Remainder when divided by 4
		0	1	2	3
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

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)

Re: Finding the solution with basic algebra and modular arithmetic

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)

Finding the Solution: Exhaustive Search is worded confusingly

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

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)