Return to Answer

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

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

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 replacing {2,3} with any finite set of prime numbers. While the analogous result for divisibility by a finite set of squared primes is probably true, it is still an open problem as far as I know. That is, if $p_1,...,p_r$ are primes and for every $a$ the integer $f(a)$ is divisible by one of $p_1^2,\dots,p_r^2$, can you show for one of the primes $p_i$ that every $f(a)$ is divisible by $p_i^2$?)

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

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

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. That is, if $f(a) \equiv 0 \bmod 6$ for all $a$, then either $f(a) \equiv 0 \bmod 2$ for all $a$ or $f(a) \equiv 0 \bmod 3$ for all $a$. On the surface, this seems kind of miraculous, doesn't it? (Same result works by CRT replacing {2,3} with any finite set of prime numbers. While the analogous result for divisibility by a finite set of squared primes is probably true, it is still an open problem as far as I know. That is, if $p_1,...,p_r$ are primes and $f(a) \equiv 0 \bmod p_1^2\cdots p_r^2$ for all $a$, can you show for one of the primes $p_i$ that $f(a) \equiv 0 \bmod p_i^2$ for all $a$?)

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

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 replacing {2,3} with any finite set of prime numbers. While the analogous result for divisibility by a finite set of squared primes is probably true, it is still an open problem as far as I know. That is, if $p_1,...,p_r$ are primes and for every $a$ the integer $f(a)$ is divisible by one of $p_1^2,\dots,p_r^2$, can you show for one of the primes $p_i$ that every $f(a)$ is divisible by $p_i^2$?)

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