Let
![[Graphics:Images/rsa4_gr_1.gif]](Images/rsa4_gr_1.gif)
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
![[Graphics:Images/rsa4_gr_2.gif]](Images/rsa4_gr_2.gif)
In the RSA system n=pq, so
![[Graphics:Images/rsa4_gr_3.gif]](Images/rsa4_gr_3.gif)
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,
![[Graphics:Images/rsa4_gr_4.gif]](Images/rsa4_gr_4.gif)
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
![[Graphics:Images/rsa4_gr_5.gif]](Images/rsa4_gr_5.gif)