How do you find "intersection"s of moduli?
For example what is the fastest way to find a number $n$ based on modular properties of $n$?
Ex: Find is the first number $n$ such that:
- $n \equiv 2 \mod 7$
- $n \equiv 4 \mod 11$
- $n \equiv 5 \mod 17$
(assumption is the modulus is prime)
This is very easy to do when they are all congruent to $0$, (hence it would just be $7*11*17$). I believe there should be a formula similar to this except using a couple constants involving the congruencies $2$, $4$, and $5$.
As was established in the comments, the Chinese Remainder Theorem says that this system of congruences has a solution because the moduli are pairwise coprime. Furthermore, any two solutions are congruent modulo $7\cdot 11\cdot 17$.
Several algorithms are described in the link, but I will use the formula for the general case:
$$x = \left[\sum_i a_i\frac{N}{n_i}\left[\left(\frac{N}{n_i}\right)^{-1}\right]_{n_i}\right]_N.$$
This looks scary, but it really isn't too difficult to work out once you substitute the numbers in. In this case we have
\begin{align*} x &= \left[a_1\frac{N}{n_1}\left[\left(\frac{N}{n_1}\right)^{-1}\right]_{n_1} + a_2\frac{N}{n_2}\left[\left(\frac{N}{n_2}\right)^{-1}\right]_{n_2} + a_3\frac{N}{n_3}\left[\left(\frac{N}{n_3}\right)^{-1}\right]_{n_3}\right]_N\\ &= \left[2\frac{7\cdot 11\cdot 17}{7}\left[\left(\frac{7\cdot 11\cdot 17}{7}\right)^{-1}\right]_{7} + 4\frac{7\cdot 11\cdot 17}{11}\left[\left(\frac{7\cdot 11\cdot 17}{11}\right)^{-1}\right]_{11}\right.\\ &\ \ \ \ \ + \left.5\frac{7\cdot 11\cdot 17}{17}\left[\left(\frac{7\cdot 11\cdot 17}{17}\right)^{-1}\right]_{17}\right]_{7\cdot 11\cdot 17}\\ &= [374[187^{-1}]_7 + 476[119^{-1}]_{11} + 385[77^{-1}]_{17}]_{1309}\\ &= [374[5^{-1}]_7 + 476[9^{-1}]_{11} + 385[9^{-1}]_{17}]_{1309}\\ &= [374\times 3 + 476\times 5 + 385\times 2]\\ &= [4272]_{1309}\\ &= 345. \end{align*}
Note that $345 \equiv 2 \bmod 7$, $345 \equiv 4 \bmod 11$, and $345 \equiv 5 \bmod 17$. By the Chinese Remainder Theorem, any other solution to the system of congruences is of the form $345 + 1309k$ for some $k \in \mathbb{Z}$.