Trap Door

Leonhard Euler, 1736.

Let

be the number of positive integers less than or equal to n which don't have any common factors with n.

Example:  If n=15, then the positive integers less than or equal to n which don't have any common factors with n are 1, 2, 4, 7, 8, 11, 13, 14.  So

In the RSA system n=pq, so

is the number of positive integers less than or equal to n which don't have p or q as a factor.

How many positive integers less than or equal to n do have p as a factor?
    p, 2p, 3p, ..., n=qp
so there are q of them.

Similarly, there are p positive integers less than or equal to n with q as a factor.

Only one positive integer less than or equal to n has both p and q as factors, namely n=pq.  So we should only count this once.

Therefore,

This is private!  You can't calculate it without knowing p and q.

Euler's Theorem:  if x is an integer which has no common prime factors with n, then

Next Section