Here is a neat observation, we can write the above equation
as:
For the general case we have:
P(a randomly selected number is relatively prime to
63) =
.
Our probability calculation is:
In our case, let A
1
be the set of multiples of 3, then
.
Likewise let A
2
be the set of multiples of 7, and
.
N(A
1× A
2) =
and we calculate
f
(63) = 63 - 21 - 9 + 3 = 36.
where N(A) is the number of elements in the set
A. We can calculate
these N's easily. The number of integers from 1 to n
that are divisible by
p1,p2,p3
is
Using the Inclusion and Exclusion Principle we
have:
Suppose that the distinct prime divisors of the
number n are
p1, p2,
...pk
. In out case we have 3 and 7, since 327 = 63. Let Ai be
the set of all numbers from 1 to n that are divisible
by pi. The
number
we wish to calculate, f
(n), is the number of elements from the set
{1, 2, 3, ..., n} that belong to none of the sets Ai.
Euler defined the totient function f(n) as the number
of positive
integers less than n that are relatively prime to n.
(1 is considered
to be relatively prime to n.) Our problem then asks
us to find f(63).
Two integers m and n are called relatively prime
if 1 is
their only common divisor. A number is selected at random
from the set {1, 2, 3, ..., 63}. Find the probability
that is
is relatively prime to 63.
