Proving that the RSA Scheme Works

For all integers , , , , , , , and , if

1. and are distinct primes
2. ,
3. and are positive integers such that and ,
5. where
6. where

then

(See congruence)

Let , and be arbitrary integers, and assume that they satisfy parts 1-6 of the hypothesis.
Now, from parts 5 and 6 of the hypothesis, we have

Since and are distinct primes, they must be coprime.
Since , we can apply splitting modulus theorem to obtain that:

How, we prove that by considering the two cases and (see divisibility)

• Case 1: If , then we have , and therefore,
  Hence, in this case, both and are congruent to giving
• Case 2: If , then and are coprime, so by Fermat's Little Theorem, we have

From part 3 of the hypothesis and the definitions of congruence and divisibility, there exists an integer such that

(Recall that we set )
Since and and are integers, then is also positive. Therefor, we can obtain:

for some positive integer .
Substituting (1) gives

and hence we also have

since it is true for both cases, we conclude that
Also, without loss of generality, this holds true for

Since we established that and satisfy the following simultaneous congruences:

By applying splitting modulus theorem, we obtain

From parts 4 and 6 of the hypothesis, we know that and both line between and , which gives the conclusion that