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 every $a$, 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) \equiv 0 \bmod p_i^2$for all f(a)$ is divisible by $a$?)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.) 2 improved formatting 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.) 1 [made Community Wiki] 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.)