Applications of the Chinese remainder theorem

Question

As the title suggests I am interested in CRT applications. Wikipedia article on CRT lists some of the well known applications (e.g. used in the RSA algorithm, used to construct an elegant Gödel numbering for sequences...)

Do you know some other (maybe not so well known) applications? Or interesting problems (recreational? or from mathematical competitions like IMO?) which can be solved using CRT. Or any good references or examples in that direction.

I hope that with this I will have better understanding of CRT and how to use it in general.

Answer 1

Parallel computation: Suppose you have a huge computation to do that involves adding, multiplying and subtracting integers. Possibly also dividing but, if so, only division by numbers in a finite set S which you already know.

Choose primes $p_1$, $p_2$, ..., $p_r$ which do not divide any element of $S$, and such that $p_1 p_2 \cdots p_r$ is surely larger than your answer. Split your computation over $r$ processors, the $i$th of which computes the answer modulo $p_i$. Use CRT to put your answer back together in the end.

This was the method used in the recent computation of the Kazhdan-Lustig-Vogan polynomials of E8.

Answer 2

Secret sharing. Suppose we have $N$ people. We want any $k+1$ of them to be able to launch a missile attack, but no $k$ of them to have this power.

Solution: Choose some large prime $p$ and a random polynomial $f(t)$ of degree $k$ with coefficients in $\mathbb{Z}/p$. Tell person $1$ the value of $f(1)$, person $2$ the value of $f(2)$ and so forth. (Also, everyone knows what $p$ is.) Set up the missiles to only launch when $f(0)$ is input. Any $k+1$ people can use the Chinese remainder theorem to compute $f$, and hence $f(0)$; any $k$ people do not have enough data to constrain $f(0)$ in any way.

Answer 3

The Chinese remainder theorem is used to resolve multiple range ambiguities in many radar systems.

Answer 4

Lagrange interpolation is a special case of the Chinese remainder theorem. (Fixing a dead link: https://artofproblemsolving.com/community/c1157h990758_the_chinese_remainder_theorem_and_lagrange_interpolation )

The Jordan normal form can be proven extremely quickly using the Chinese remainder theorem for modules over a commutative ring. This proceeds by first proving the Jordan-Chevalley decomposition, and then the rest is a simple exercise of showing what the Jordan blocks actually look like.

The first one is very surprising to people, but if you state Lagrange interpolation correctly, it's easy to see that the idea is not only similar but identical.

Answer 5

Here are some applications I don't see listed among the other answers.

1. Everyone knows $5^2$ ends in 5 and $6^2$ ends in 6. Your task: find multi-digit numbers whose squares end in themselves (e.g., $25^2$ ends in 25, $76^2$ ends in 76, ...). This problem can be given to students -- even children -- who know no particular mathematics and they discover experimentally for $n$ = 2, 3, 4, ... that there are usually two $n$-digit solutions (sometimes fewer than 2 solutions, but never more than 2). As for whether this pattern persists for all $n$, both that there usually are solutions and that there are at most two solutions among $n$-digit numbers, turn the problem into a congruence condition and then think about CRT.

2. If $f(x)$ is in ${\mathbf Z}[x]$ and all of its values $f(a)$ for $a$ in ${\mathbf Z}$ are multiples of either 2 or 3, then CRT implies all of its values are multiples of 2 or all of its values are multiples of 3. On the surface, this seems kind of miraculous, doesn't it? (Same result works by CRT if you replace {2,3} with any finite set of pairwise relatively prime integers.)

3. The Solovay-Strassen probabilistic primality test. Verifying that this test admits a witness for odd composite moduli uses CRT. When I teach undergraduate number theory, the SS test has always been the last topic in the course and it's a neat application of CRT.

4. If $a$ is not a square in $\mathbf Z$ then there are infinitely many primes $p$ such that $a \bmod p$ is not a square. This is an application of the Chinese remainder theorem and quadratic reciprocity. (This can be superseded in a quantitative sense if you use Dirichlet's theorem on primes in arithmetic progression.)

5. If $m \mid n$ then the reduction map ${\mathbf Z}/n{\mathbf Z} \rightarrow {\mathbf Z}/m{\mathbf Z}$ is easily surjective. Please try to prove by elementary methods that the reduction map on units, $({\mathbf Z}/n{\mathbf Z})^\times \rightarrow ({\mathbf Z}/m{\mathbf Z})^\times$, is surjective without using CRT. Using CRT it is quite easy. (You can yank in Dirichlet's theorem on primes for a fast proof, but that's a rather deep result compared to CRT, so it wouldn't count as an elementary proof avoiding CRT.)

Answer 6

There are some cute exercises based on the Chinese remainder theorem, e.g.,

(1) there exist an arbitrarily large number of consecutive integers, none of which is squarefree (1955 Putnam Competition),

(2) there exist an arbitrarily large number of consecutive integers, none of which is powerful ($n$ is powerful if for every prime $p$ dividing $n$, we have $p^2 \mid n$),

(3) there exist an arbitrarily large number of consecutive positive integers, none of which is a sum of two squares,

(4) the number of integers $1\cdot 2, 2\cdot 3, \dots, n\cdot (n+1)$ divisible by $n$ is $2^{\omega(n)}$, where $\omega(n)$ is the number of distinct prime divisors of $n$.

Answer 7

In the proof of Gödel's First Incompleteness Theorem, you need to choose a way to encode formulas and proofs as numbers. The easy way to do this is to take 2^i₀3^i₁5^i₃...p_j^i_j. However you can instead use the Chinese Remainder Theorem to pick a number congruent to i₀ mod p₀, congruent to i₁ mod p₁, etc. (Of course, you need to pick big enough primes then.) The advantage of doing this is you no longer need exponentiation in your theory, just multiplication and addition.

Answer 8

Quadratic Reciprocity

Perhaps the best application of the CRT is in a proof of the Gauss' Quadratic Reciprocity, a proof due to Rousseau (my version found on my blog here) that uses just the CRT. It is very rare that proofs of the QR drop out without a lot of effort :)

Answer 9

You already bring this idea up when you mention RSA but I want to make the point more generally: There are very good methods for solving polynomial equations modulo primes and prime powers. The only good way to solve an equation modulo $N$ is to factor $N$; solve modulo each prime power dividing $N$, and use Chinese remainder to put a solution back together. This is true even for computing square roots.

Answer 10

CRT combined with Dirichlet's theorem allows you to prove the existence of infinitely many primes satisfying any system of congruences that has a solution; I sketched a proof that this implies that the square roots of integers have no nontrivial linear dependences here.

Answer 11

Here is a neat example that predates David Speyer's example of fast parallel arithmetic, but uses the same trick.

Richard J. Lipton, Yechezkel Zalcstein: Word Problems Solvable in Logspace. J. ACM 24(3): 522-526 (1977)

In this paper, the Chinese remainder theorem is used to prove that the word problem on several types of groups are solvable in logspace. (The Chinese remainder theorem is not explicitly invoked, but one can use it to justify the algorithms.) For instance, the paper states:

Corollary 6. The word problem for finitely generated free groups is solvable in logspace.

The word problem for a finite group is to determine if a given product of group elements equals the identity. The results are proved by embedding a group into a group of matrices over the integers, then computing the matrix product modulo all small primes.

Answer 12

Many properties of $\mathbb{Z}/n$ can be broken down to properties of $\mathbb{Z}/p^i$ using the Chinese Remainder Theorem. Here is an example that I have no idea how to prove otherwise:

IMO Shortlist 1997 problem 15 is equivalent to proving that if some given integer is a square residue modulo $n$ and a cubic residue modulo $n$ at the same time, then it is a $6$-th power residue modulo $n$ as well. More generally, if $n$, $u$, $v$ are three positive integers, and some given $a\in\mathbb{Z}/n$ is both a $u$-th power and a $v$-th power in $\mathbb{Z}/n$, then $a$ is a $\mathrm{lcm}\left(u,v\right)$-th power in $\mathbb{Z}/n$.

Answer 13

The chinese remainder theorem can be generalized as follows: Let $G$ be a group with normal subgroups $H,K$ of $G$. Then the canonical map $G/(H \cap K) \to G/H \times_{G/(HK)} G/K$ is an isomorphism. The proof is trivial! With the same argument: Let $R$ be a ring with ideals $I,J$, then the canonical map $R/(I \cap J) \to R/I \times_{R/(I+J)} R/J$ is an isomorphism. Now this reveals a geometric meaning of the cinese remainder theorem:

Let $X$ be a scheme and $A,B$ two closed subschemes of $X$. Then $A \cup B$ is a closed subscheme of $X$ (intersect the ideal sheaves) and we have $A \cup B = A \coprod_{A \cap B} B$.

Thus the union of two closed subschemes is the pushout of $A$ and $B$ along $A \cap B$, which is very intuitive.

Answer 14

One application : to find the product of all elements in the multiplicative group $({\mathfrak o}/{\mathfrak a})^\times$, where $\mathfrak o$ is the ring of integers in a number field and ${\mathfrak a}\subset{\mathfrak o}$ is an ideal. The case ${\mathfrak o}={\mathbb Z}$ is Wilson's theorem. See for example arXiv:0711.3879v1 [math.NT].

Answer 15

The Chinese Remainder Theorem gives a way to compute matrix exponentials.

Indeed, let $A$ be a complex square matrix, put $B:=\mathbb C[A]$. This is a Banach algebra, and also a $\mathbb C[X]$-algebra ($X$ being an indeterminate). Let $S$ be the set of eigenvalues of $A$, $$\mu=\prod_{s\in S}\ (X-s)^{m(s)}$$ the minimal polynomial of $A$, and identify $B$ to $\mathbb C[X]/(\mu)$.

The Chinese Remainder Theorem says that the canonical $\mathbb C[X]$-algebra morphism $$\Phi:B\to C:=\prod_{s\in S}\ \mathbb C[X]/(X-s)^{m(s)}$$ is bijective.

Computing exponentials in $C$ is trivial, so the only missing piece in our puzzle is the explicit inversion of $\Phi$.

Fix $s$ in $S$ and let $e_s$ be the element of $C$ which has a one at the $s$ place and zeros elsewhere. It suffices to compute $\Phi^{-1}(e_s)$. This element will be of the form $$f=\frac{\mu}{(X-s)^{m(s)}}\ g\ \mbox{ mod }\mu$$ with $f,g\in\mathbb C[X]$, the only requirement being $$g\equiv\frac{(X-s)^{m(s)}}{\mu}\mbox{ mod }(X-s)^{m(s)}$$ (the congruence taking place in the ring of rational fractions defined at $s$). So $g$ is given by Taylor's Formula.

Answer 16

The Mayan calendar system uses a number of different periodic processes, and provides a simple but very important example of a practical use of the CRT.

The Tzolkin, or Day Count, has twenty weekdays (Ik, Akbal,... Auau) and thirteen numbers, 1-13. Each day, the day name advances, and so does the number. For example, 7 Ik is followed by 8 Akbal. These name/number pairs repeat in a 260 day cycle, which has been in continuous uniterrupted use since at least 600BC.

The Haab, or Vague Year, is a 365 day year consisting of 19 months (Pop, Uo, ..., Cumku, Uayeb). The first 18 months have 20 days and Uayeb has five days. The Haab runs 0 Pop, 1 Pop, ..., 19 Pop, 0 Uo, 1 Uo,..., 4 Uayeb and then repeats to 0 Pop.

Together, the Tzolkin and Haab form the calendar round, with dates given by Tzolkin then Haab, for example, 7 Ik 0 Cumku. This cycle repeats every 18980 days, about 52 years, which means that a calendar round date is good for most practical purposes (such as birth dates).

The earlier Mayan period, from around the 1st century BC to the 13th century AD, also featured a system known as the long count, recently made somewhat famous by the fact that it finished a 5126 year cycle on December 21, 2012. Long count dates have Kin (days) which run 0-19. 20 Kin make one Uinal, 18 Uinal make one Tun, 20 Tun make one Katun, and 20 Katun make one Baktun. Dates are written with Baktun first, as, for example, 9.7.17.12.14. After 13 Baktun, the date goes back to zero, so that 12.19.19.17.19 was followed by 0.0.0.0.0.

One major problem with studying the Mayan calendar is that the long count dates fell out of use hundreds of years before the Spanish arrived, and it is nontrivial to decide which Mayan long count dates correspond to which dates in the modern western calendar system - the 'correlation problem'.

The key document, the Chronicle of Oxcutzcab, says that a tun ended 13 Ahua 8 Xul in AD 1539, thus tying together the long count (tun ending), the calendar round, and the Julian calendar. From ancient records, the long count is known to have begun on 4 Ahua, 8 Cumku. So, given 0.0.0.0.0 = 4 Ahua 8 Cumku, one needs to solve $x$.0.0 = 13 Ahua 8 Xul. The day number gives the equation $360 x \equiv 9 \pmod{13}$. Since 8 Xul is 125 days after 8 Cumku, the Haab gives the second equation $360 x \equiv 125 \pmod{365}$.

So, there's a simple little use of CRT: Solve for $x$, and find $x \equiv 924 \pmod{949}$.

To finish the story, the year AD 1539 contains the long count tun 924 = 2.6.4.0.0 plus some multiple of 949 tun = 2.7.9.0.0. There is enough historical evidence to guess the date to within 949 tun (about 935 years), and so one learns that 11.16.0.0.0 is in AD 1539. Finally, the calendar round is still in use and so one can determine that 11.16.0.0.0 is November 12, 1539. I'll leave it as an exercise to determine that December 21, 2012 really was 0.0.0.0.0.

Answer 17

A variant of the CRT that has many practical applications is the "explicit CRT" (see http://cr.yp.to/antiforgery/meecrt-20060914-ams.pdf, for a good introduction).

One scenario where the explicit CRT (mod m) can be used, is the following. Suppose we know the value of an integer x modulo primes p_1, ..., p_n, whose product exceeds, say, 4|x|. Now we could use a standard CRT computation to determine x, but suppose we actually wish to know x mod m, where m is some integer not among the p_i. The explicit CRT lets us compute x mod m using arithmetic operations that involve operands that are all about the same size as m (rather than x). This is useful when x >> m; if x is a 100 digit number but the p_i's and m are all 3 or 4 digits numbers, you could compute x mod m on a pocket calculator with an 8 digit display, given the values x mod p_1, ..., x mod p_n.

This technique is especially useful when one needs to compute many large integers x modulo the same m (the integers x might be the coefficients of a polynomial and m might be the characteristic of a finite field, for example). This approach is used in http://arxiv.org/abs/0903.2785 to compute Hilbert class polynomials, and in http://arxiv.org/abs/1001.0402 to compute modular polynomials, both of which are notoriously large but can be efficiently computed with the explicit CRT.

Answer 18

Here is an adorable application of the CRT in combinatorial number theory: In an exact covering system of congruences the two largest moduli must be identical. In other words, if you partition the integers into arithmetic series, then two of the series must have the same 'step size'. This is often given as an application of (basic) complex analysis but all you really need is the CRT!

http://www.emis.de/journals/EJC/Volume_8/PDF/v8i2a1.pdf

Answer 19

Pohlig–Hellman discrete logarithm computation is based on the CRT.

A degree n discrete Fourier Transform is identical to polynomial evaluation at primitive $n$-th roots of unity. The inverse transform is interpolation or the CRT (as mentioned in earlier posts).

Montgomery reduction uses the CRT to reduce an integer modulo $x\bmod{N}$ without division by $N$ by creating an integer equivalent to $x\bmod{N}$ and $0\bmod{2^r}$, then dividing by $2^r$.

Answer 20

I often deal with combinatorial numbers $x$ are difficult to compute exactly, but it's possible to find congruences satisfied by them. You can combine the congruences using the Chinese Remainder Theorem into one concise congruence. If one day someone does compute the number $x$ by a lengthy computation, they can check that $x$ satisfies the congruence.

For instance, the number of reduced Latin squares $R_{12}$ of order $12$ is unknown, but it satisfies $R_{12} \equiv 50400 \pmod {55440}$.

Answer 21

Mark Iwen uses the CRT to construct a Sparse Fourier Transform, see:

A Deterministic Sub-linear Time Sparse Fourier Algorithm via Non-adaptive Compressed Sensing Methods, M. A. Iwen, http://arxiv.org/abs/0708.1211

Answer 22

CRT is used to generate Payam Numbers. A Payam number k can generate very prime sequences of the form k*M(x)*2^n+/-1, with n variable, M(x) a multiple of certain primes. The pursuit of very prime series using Payam numbers is a mathematical recreation currently located at

http://www.mersenneforum.org/showthread.php?t=9755

Answer 23

Here’s a nice problem that was among some IMO practice problems. I don’t know the source.

Problem: Prove that for each natural number $n$, there is some natural number $r$ for which the $n$ integers $r+1^2,r+2^2,\ldots ,r+n^2$ are all squarefree.

Solution (sketch): For a large prime $p$, the probability that none of these $n$ integers is divisible by $p^2$ is $1-\frac{n}{p^2}$. Assuming independence for the $p_i$s we get $(1-\frac{n}{2^2})(1-\frac{n}{3^2})(1-\frac{n}{5^2})\ldots$, which converges to a positive number, so there must exist solutions.

To make this into a rigorous argument one needs CRT.

Answer 24

Also there are some examples with visible and nonvisible lattice points:

• Fritz Herzog and B. M. Stewart, Patterns of Visible and Nonvisible Lattice Points, The American Mathematical Monthly, Vol. 78, No. 5 (May, 1971), pp. 487-496 and correction.

• Peter Schumer, Strings of Strongly Composite Integers and Invisible Lattice Points, The College Mathematics Journal, Vol. 21, No. 1 (Jan., 1990), pp. 37-40.

Answer 25

One answer I don't see here: Lagrange interpolation. If one takes, for example, the ring $\mathbb{Q}[x]$, and realizes CRT as a statement about rings and direct sums of $R/P$ over a set of co-prime $P,$ then one can construct polynomials which have cycles of arbitrary length in the rationals (or any number of cycles of arbitrary length). Lagrange interpolation has other applications, but the proof is CRT.

Answer 26

One application that I heard about (but haven't actually used myself) is in computing combinatorial numbers $x$ that have very many digits. Sometimes, instead of dealing with arbitrary precision arithmetic, it is easier to compute $x \pmod \mu$ for many small moduli $\mu$ (which can be substantially faster than dealing with $x$ itself) then afterwards combine the congruences using the Chinese Remainder Theorem to find $x$ itself. Although this requires that you have an upper bound on $x$ or some idea of how large it should be.

Answer 27

Ulrich Oberst wrote an article on that in Expositiones no. 3, 1985 "Anwendungen des chinesischen Restsatzes".

Answer 28

Actually, not only the Lagrange interpolation, but more generally the Hermite interpolation problem (i.e. with prescribed jets at the nodes) may be treated as an application of the CRT. I happened to wirte some lines on it in the wiki article (where others applications and references are also given).

Answer 29

In computer science, more specifically, the theory of finite automata, the Chinese Remainder Theorem proves useful when thinking about finite automata or regular expressions over a 1-letter alphabet. The prerequisites (finite automata, regular expressions, NP-completeness) for understanding these applications are usually taught in "introduction to theoretical computer science" university courses.

For example, the universality problem for unary regular expressions is coNP-complete. The polynomial-time reduction uses chinese remaindering to encode a boolean formula into a regular expression. L. J. Stockmeyer, A. R. Meyer: Word problems requiring exponential time (Preliminary Report), Proceedings of the th annual ACM symposium on Theory of computing (STOC '73), pp. 1-9.

Also, the worst-case size blowup when moving from nondeterministic to deterministic finite automata is related to Landau's function, and the proof uses the Chinese Remainder Theorem. Marek Chrobak: Finite Automata and Unary Languages. Theoretical Computer Science 47(3): 149-158 (1986)

Answer 30

Chinese Remainder Theorem has been used in Uniswap v3 to create a 512-bit multiplication (that works for numbers below $2^{256}(2^{256} - 1)$) between 256-bit numbers, the maximum integer type in the Ethereum Virtual Machine. Here is a link for the detailed explanation: https://xn--2-umb.com/17/full-mul/