Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
4  
This looks a lot like the Pigeon-hole thread, so...community wiki at least? –  Gjergji Zaimi Dec 29 '09 at 9:52
2  
The Chinese remainder theorem is best learned in the generality of ring theory. That is, for coprime ideals a1,...,an of a ring R, R/a is isomorphic to the product of the rings R/ai where a is defined to be the product (and by coprimality also the intersection) of the ideals ai –  Harry Gindi Dec 29 '09 at 10:43
2  
Any question with the [big-list] tag should always be community wiki. I've converted it. –  Anton Geraschenko Dec 29 '09 at 17:04
    
Some months later: an outstanding list of applications! For those who are fond of wikipedia, I think it could provide nice hints to expand the section "Applications" in the wiki article linked in the question. –  Pietro Majer Jul 30 '10 at 10:25

28 Answers 28

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.

share|improve this answer
    
This may be a dumb comment, but... Why not do the following instead? Choose a large prime $p$ and elements $a_1,a_2,...,a_{k+1}$ in $\mathbb{Z}/p$. Tell person $j$ the value of $a_j$, for each $j$. Set up the missiles to only launch when $\sum_{j=1}^{k+1}a_j$ is input. I am not sure if there is an essential difference between this and your suggestion. –  senti_today Aug 17 '10 at 21:23
    
Because N is larger than k+1. –  David Speyer Aug 17 '10 at 21:38
3  
FYI this is called Shamir secret-sharing. Am I right in thinking that the reason we work over $\mathbb{Z}/p$ is that one can sensibly talk about random polynomials (with the implicitly-chosen uniform distribution on each coefficient), and not have to specify a more-or-less arbitrary distribution if we, say, took real coefficients? –  Cam McLeman Dec 2 '10 at 13:49
2  
First, I think this example shows that the Chinese Remainder Theorem for polynomials is not the same as the one for integers (which cannot be used in the above manner). But more importantly, this form of secret sharing does not depend on any CRT. The idea is just to have a point in a $d=k+1$-dimensional vector space as code, and a bunch of linear equations that this point satisfies as secrets, such that any $d$-subset of them forms a Cramer system that can be uniquely solved, while fewer than $d$ of them of course do not allow this. –  Marc van Leeuwen Oct 7 '13 at 12:33
1  
Agree with @Marc. Many of the other answers are cool but this is one is hardly more spectacular than any protocol using mere linear independence. No idea why people upvote it so much. –  Marek Dec 10 '13 at 18:18

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.

share|improve this answer
2  
I was just about to add the computation of the character table of E8 to the list when I saw this answer. So instead, a belated +1. –  Pete L. Clark Jul 31 '10 at 12:09
7  
Dirk Kinnaes and I used this method to find that there are 28447358001452528666612175249660024223928133055989514238081589468009352908684070‌​327935360183969579439273878855677840504403763036051051019859232961838168897903868‌​848253786023988596123888781265696937219679848446213284355729999107549300755062792‌​6803688745250953668796106910118867088442300850000 binary matrices of order 34 such that each row and each column have 17 ones. However I did meet one computer-illiterate mathematician who believed me when I claimed that we counted them one at a time. –  Brendan McKay Jul 12 '12 at 11:52
1  
Actually the mentioned $E_8$ computations were done in serial, not in parallel. The constraint was memory, not time: the CRT allowed $1$-byte coefficients to be used instead of $4$-byte integers, which given the huge amount of coefficients required was a crucial memory savings at the time. –  Marc van Leeuwen Oct 7 '13 at 12:41
    
How can you divide by the elements in S? I assume you meant multiplication by modular inverse, which isn't actually division, unless it happens to divide exactly. –  Realz Slaw Mar 5 at 17:03

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

share|improve this answer
12  
To elaborate on this, because it's more applied than the rest: Many radar systems work by sending EM pulses out at regular intervals, waiting in between pulses to look for reflections from objects. You want to calculate an object's distance from the time it takes to see a reflection. If time between pulses is very long, this works, but if you're observing something dynamic you want fast updates, so you need shorter time between pulses. But then you don't know which pulse's reflection you're seeing, so object range is only known modulo (speed of light)*(pulse interval). (cont'd) –  Ian Jul 30 '10 at 2:14
3  
(cont'd from above) The solution is to send out a few different types of pulses (say, with different wavelengths of light), with each type of pulse having it's own pulse interval, and making those intervals coprime. Then you can use the CRT to calculate range mod some very large distance (where you know, practically speaking, that you won't be registering any reflections from such large distances). –  Ian Jul 30 '10 at 2:23
1  
This is detailed on p 306 of Roger Sullivan's book Microwave radar: imaging and advanced concepts –  Steve Huntsman Oct 16 '10 at 2:10

Lagrange interpolation is a special case of the Chinese remainder theorem.

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.

share|improve this answer
2  
This sounds interesting. Can you give a reference? –  Idoneal Dec 29 '09 at 15:57
2  
or elaborate on this? –  Lior Bary-Soroker Dec 29 '09 at 19:13
    
Which one would you like to hear about? –  Harry Gindi Dec 29 '09 at 20:20
3  
I explained the connection between CRT and Lagrange interpolation on my old blog once: artofproblemsolving.com/Forum/weblog_entry.php?t=237669 . –  Qiaochu Yuan Dec 29 '09 at 23:07
2  
Why is this comment on my answer rather than the op? –  Harry Gindi Dec 30 '09 at 15:10

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|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$.

share|improve this answer
2  
By way of contrast to (2), I believe it is unknown whether there exist three consecutive integers each of which is powerful. –  Gerry Myerson Jul 12 '12 at 6:21

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

share|improve this answer
    
I think you are using the symbol $\equiv$ in a nonstandard way in 2 above. –  Idoneal Jan 17 '10 at 5:49
2  
Huh? The notation looks correct to me. It's the congruence notation from modular arithmetic. To say a number is 0 mod m means it is a multiple of m, and that's the situation I'm describing in 2. In what way does the usage look nonstandard? (I said at the start that a runs over integers, and that remains true anywhere later on as well.) –  KConrad Jan 17 '10 at 6:17
    
The statement starting at "That is," in 2. is not what you meant to write, based on what you say in the first sentence. It says "If $6$ divides $f(a)$ for all $a$, then either $2$ divides every $f(a)$, or $3$ divides every $f(a)$", which is certainly true and does not use CRT. I think that's why Idoneal was suggesting that it was a modified version of congruence. You could instead say "That is, if $f(a) \equiv 0, 2, 3$, or $4 \mod{6}$ for each $a$, then either..." –  Zack Wolske Jul 12 '12 at 1:35
    
Since this is a few years old, do you know if the question on squares is still open? –  Zack Wolske Jul 12 '12 at 1:36
    
@Zack: Thanks for pointing that out. I fixed the statement of 2. And as far as I know the question on squares is still unproved. –  KConrad Jul 12 '12 at 2:51

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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 2i03i15i3...pjij. However you can instead use the Chinese Remainder Theorem to pick a number congruent to i0 mod p0, congruent to i1 mod p1, 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 adition.

share|improve this answer
    
I assumed that this is what was meant by "used to construct an elegant Gödel numbering for sequences" in the original question. –  Andreas Blass Sep 18 '10 at 23:03

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$.

share|improve this answer

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.

share|improve this answer
    
Isn't this just the standard recipe "Transform to the JNF, compute exponentials of Jordan blocks and transform back" ? –  Johannes Hahn Mar 31 at 19:45
    
@JohannesHahn - Dear Johannes: Thanks for your comment. I think it's much harder to put a matrix in JNF than to compute its exponential. I know no closed formula for the JNF. The exponential depends only on the minimal polynomial, which is a much coarser invariant than the JNF. –  Pierre-Yves Gaillard Apr 1 at 5:31

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].

share|improve this answer

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

share|improve this answer
1  
It is an application of CRT, but it does not qualify as "perhaps the best". Even among proofs of quadratic reciprocity, this is not one of the nicer ones (in terms of elegance or insight). I've seen a lot of such proofs and this wouldn't go in my top 5. –  KConrad Jan 17 '10 at 19:17
12  
Wow, tough crowd. –  Pete L. Clark Jan 29 '10 at 6:22

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$.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
While I absolutely don't want to ruin Doron's wonderful polemic, let me add that the "complex-analytic" proof he quotes is completely algebraic. Just look at it from the correct angle: We take the equation (MNDR) and rewrite it as $\frac{1}{1-z}-\sum_{i=1}^{n-1} \frac{z^{b_i}}{1-z^{a_i}} = \frac{z^{b_n}}{1-z^{a_n}}$. Bringing the left hand side to a common denominator, this denominator is going to be a polynomial which is nonzero on any primitive $a_n$-th root of unity, so if we multiply the equation with the $a_n$-th cyclotomic polynomial, the left hand side becomes $0$. But the right ... –  darij grinberg Apr 4 '11 at 22:56
1  
... one doesn't. –  darij grinberg Apr 4 '11 at 22:56
    
What we DO use here is the existence of a primitive $a_n$-th root of unity. This is somewhat tricky if we wish to avoid analysis, but many books do it right. –  darij grinberg Apr 4 '11 at 22:57
    
That's a good point! –  Burton Newman Apr 7 '11 at 0:35

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
    
For parallel computation, see David Speyer's comment amount the Kazhdan-Lusztig-Vogan polynomials of E_8 below. –  Michael Lugo Dec 29 '09 at 22:23
    
As another example of this, I heard that people used to compute Bernoulli numbers using the von Staudt-Clausen Theorem ( en.wikipedia.org/wiki/Von_Staudt%E2%80%93Clausen_theorem ). –  darij grinberg Mar 20 '10 at 18:29

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}$.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
    
Way down in the second answer. –  Qiaochu Yuan Jan 29 '10 at 5:35
    
ah! my apologies, I missed that one. –  Ben Weiss Jan 29 '10 at 6:37

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.