1. Not finding help here? Sign up for a free 30min 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!

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

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

    SammyS

    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Inclusion-exclusion positive integers
  1. Inclusion exclusion (Replies: 0)

Loading...