1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Inclusion-exclusion positive integers

  1. Jan 30, 2012 #1
    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


    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. jcsd
  3. Jan 30, 2012 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    How many multiples of p are less than n ? ...
  4. Jan 30, 2012 #3
    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook