Question

Consider all integers between 1 and pq where p and q are two distinct primes. We choose one of them, all with equal probability.

a) What is the probability that we choose any given number?

b) What is the probability that we choose a number that is

i) relatively prime to p?

ii) relatively prime to q?

iii) relatively prime to pq?

Answer 1

a)

Total numbers between 1 and pq are pq

Probability that we choose any given number = 1/pq

b)

i)

All numbers between 1 and pq will be relatively prime to p except p and pq.

Total numbers between 1 and pq that are relatively prime to p are pq - 2

Probability that we choose a number that is relatively prime to p = (pq - 2) / pq

ii)

All numbers between 1 and pq will be relatively prime to q except q and pq.

Total numbers between 1 and pq that are relatively prime to q are pq - 2

Probability that we choose a number that is relatively prime to q = (pq - 2) / pq

iii)

All numbers between 1 and pq will be relatively prime to pq except pq.

Total numbers between 1 and pq that are relatively prime to pq are pq - 1

Probability that we choose a number that is relatively prime to pq = (pq - 1) / pq