If p and q are different primes (so each > or = 2) and if n= pq, then the number of integers of the set 2, 3, 4,..., n which have no common factors (other than 1) in with n is
A. n-pq
B. pq-(p+q)
C. pq-(p+q+1)
D. pq-3
E. pq-4
To find the number of integers in the set 2, 3, 4, ..., n that have no common factors with n (other than 1), we can use Euler's totient function.
Euler's totient function phi(n) counts the number of positive integers less than or equal to n that are coprime (have no common factors) with n.
For any number n = pq, where p and q are prime numbers, phi(n) can be calculated using the formula:
phi(n) = (p - 1) * (q - 1)
In this case, since n = pq, we have:
phi(n) = (p - 1) * (q - 1)
Now, to find the number of integers in the set 2, 3, 4, ..., n that have no common factors with n, we need to subtract phi(n) from n.
So, the number of integers in the set that have no common factors with n is:
n - phi(n)
= n - (p - 1) * (q - 1)
Substituting n = pq, we get:
pq - (p - 1) * (q - 1)
Expanding the expression:
pq - (pq - p - q + 1)
= pq - pq + p + q - 1
= p + q - 1
Therefore, the correct answer is:
C. pq - (p + q + 1)