Inclusion-exclusion positive integers

[changeofplans]

Homework Statement

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.

Homework Equations

Inclusion-Exclusion

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 - |p_i U q_i|

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

 

[SammyS]

Homework Statement

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.

Homework Equations

Inclusion-Exclusion

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 - |p_i U q_i|

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

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

 

[changeofplans]

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

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?