# Homework Help: Inclusion-exclusion positive integers

1. Jan 30, 2012

### changeofplans

1. The problem statement, all variables and given/known data

Suppose that p and q are prime numbers and that n = pq. Use the principle of inclusion-exclusion to find the number of positive integers not exceeding n that are relatively prime to n.

2. Relevant equations

Inclusion-Exclusion

3. The attempt at a solution

The way I see it, n = pq is contained in a set of all the prime numbers from 1 to pq, plus the multiples that are not prime. So:

n = pq - |pi U qi|

I'm not exactly sure where to go from here, though. Any help is appreciated.

2. Jan 30, 2012

### SammyS

Staff Emeritus
How many multiples of p are less than n ? ...

3. Jan 30, 2012

### changeofplans

Would it be the floor of $\frac{pq}{p}$? And then the number of multiples of q less than n would be the floor of $\frac{pq}{q}$.

If that's the case, I think I see what i'm supposed to do; add up the primes in p, and add up the primes in q. Because they're not mutually exclusive, we then need to take out the primes shared by both p and q.

Any ideas on how to do that? Am I missing something?