# The RSA Theorem

Let and be distinct primes, and let satisfy . Then for any , .

For some reason, even in published works, this important cryptographic result is often only half proved. Here is a full proof.

Proof: We consider two cases: (i) is relatively prime to both and (and hence relatively prime to ), and (ii) is a multiple of one of the primes, say . We note that can’t be a product of both primes, for then it would be greater than their product, thus violating the statement of the theorem.

(i) By definition, for some integer . Since , then by Euler’s theorem

.

(ii) Clearly

(1)

since both sides are equal to . We can also write , and since is relatively prime to , then by Euler’s theorem again and so

(2)

By the Chinese remainder theorem, (1) and (2) together prove as required.

## 2 thoughts on “The RSA Theorem”

1. mvngu says:

Possible typos:

[1] …relatively prime to both p and q (and hence…
comment: don’t know where the closing parenthesis should be placed; I think it’s missing.

[2] …for then it would be greater then their product…
—>
…for then it would be greater than their product…
comment: for the second “then”, change “e” to “a”

2. amca01 says:

Thanks very much – I’ll change those at once.