Question

Question: Suppose that \(p\) and \(q\) are primes and \(n = pq\). What is the probability that a randomly chosen positive integer less than \(n\) is not divisible by either \(p\) or \(q\) ?

Short answer

Answer

The probability of a randomly chosen positive integer less than \(n\) is not divisible by either \(p\) or \(q\) is \( = \frac{{(p - 1)(q - 1)}}{{pq - 1}}\).

Step-by-step solution

Given data

Integers \(p\) and \(q\) are primes and \(n = pq\).

Concept of Probability

Probability is simply how likely something is to happen. Whenever we’re unsure about the outcome of an event, we can talk about the probabilities of certain outcomes—how likely they are. The analysis of events governed by probability is called statistics.

Calculation for the number of integers divisible

The integers divisible by \(p\) are \(p\;,\;2p\;, \ldots .(q - 1)p\).

The integers divisible by \(q\) are \(q\;,\;2q\;, \ldots ..(p - 1)q\).

\(p\;,\;q\)are primes, so none of the above numbers are divisible by either \(p\) or \(q\).

Total number of integers divisible either \(p\) or \(q\)\( = p - 1 + q - 1\).

Total number of integers divisible either \(p\) or \(q\)\( = p + q - 2\).

Total number of integers \( = n - 1\).

Total number of integers \( = pq - 1\).

Calculation for the number of integers not divisible

The numbers are not divisible by either \(p\) or \(q\)\( = (pq - 1) - (p + q - 2)\).

The numbers are not divisible by either \(p\) or \(q\)\( = (p - 1)(q - 1)\).

Therefore, the probability of a randomly chosen positive integer less than \(n\) is not divisible by either \(p\) or \(q\) \( = \frac{{(p - 1)(q - 1)}}{{pq - 1}}\).