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 = p q, 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, 2 p, 3 p, ..., n = q p
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 = p q.  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

A Short Proof of Euler's Theorem (not Euler's)

(for those who know group theory)

Joseph-Louis Lagrange, 1770; Evariste Galois, c. 1830

Multiplication modulo n means working in the group , which has elements.  Then Lagrange's Theorem implies that the order of any x divides ; thus is the identity, which is the same as our theorem.

Next Section