Splitting Modulus Theorem

For all integers and positive integers and , if , then the simultaneous congruences:

have exactly the same solutions as the single congruence

(See GCD)

Note that SMT is actually and if and only if statement, so its converse is also true.

Find all integers such that

This is a non-linear congruence, and going through every possibility in mod 35 is not a good idea. Since and , we can use SMT, we can use SMT. That means the solution to the one non-linear congruence is the same as the two, simultaneous non-linear congruences:

For the first congruence:

We see that the solution is (See set builder notation)

For the second congruence:

We see that the solution is

This leaves us with two linear congruences:

Since , we can apply CRT and obtain that the solution to these simultaneous congruences is the set of all integers such that , where is one particular solution.

To find a suitable value for , note that are the choices of integers between and that are congruent to .
How, , , , , so is a solution to both linear congruences simultaneously.

We conclude that the set of solutions for the original non-linear congruences are all integers such that .

Let be an integer. Prove that If , then
(See GCD)

Let $a4 be an arbitrary integer, and assume that .
Since and , we can apply SMT.

Since , by Bézout's lemma, there exists integers and such that:

Hence, , and from coprimeness characterization theorem, we have , and .

Since , and is prime, by Fermat's little theorem, we obtain.
Then, by congruence power, taking the 5th power on both sides, we obtain:

Similarly, since and is prime, by FℓT, we obtain . Then by CP, cubing both sides gives