Two integers m and n are called relatively prime if 1 is their only common positive divisor. Thus 8 and 5 are relatively prime, whereas 8 and 6 are not. A number is selected at random from the set {1, 2, 3, . . . , 63}. Find the probability that it is relatively prime to 63.
I'm not sure why this problem is giving me trouble. I know there are 36 numbers in that set that are relatively prime to 63, so that equals a 4/7 chance of picking a prime. I did this using the "brute force" method, but I'm not sure of how to set up a way of doing it using the $P(A\cup B) = P(A)+P(B) – P(A \cap B) $ formula.
Best Answer
Since $63 = 3^2\cdot7$, an integer $n \in \{1,\ldots,63\}$ is relatively prime to $63$ if and only if $3 \nmid n$ and $7 \nmid n$.
Let $A$ be the event that $n$ is divisible by $3$, and let $B$ be the event that $n$ is divisible by $7$. Thus
\begin{align} P(A \cup B) &= P(A) + P(B) - P(A \cap B) \\ &= \frac{1}{3} + \frac{1}{7} - \frac{1}{21} = \frac{7+3-1}{21} = \frac{9}{21} = \frac{3}{7} \end{align}
is the probability that a random integer in $\{1,\ldots,63\}$ shares a divisor with $63$, and therefore the probability that a random integer in $\{1,\ldots,63\}$ is relatively prime to $63$ is $1 - \frac{3}{7} = \frac{4}{7}$.
The calculation follows from observing that every third number in $\{1,\ldots,63\}$ is divisible by $3$, every seventh is divisible by $7$, and every "three times seven"-th number is divisible by $3$ and $7$.