Chinese Remainder Theorem
Table of Contents
1. Theorem Statement
2. Applications
Note if we are given
ie
There exist an arbitrarily large number of consecutive integers, none of which is squarefree.
Let
ie
Of which a unique solution is guarenteed by the Chinese Remainder Theorem.
3. Extension
If
Now we prove:
where
ie
The forward case is trivial:
Now applying modulo
For the backward case, note that the distinct elements of
where
Hence (1) is proved. Suppose we have some system of linear congruences which satisfy the predicates required by CRT except there is some pair of congruences whose moduli are not coprime:
Then by (1), we can reduce these two congruences into more congruences, whose moduli are either pairwise coprime or of the form:
Which has solutions