Relative primes
What is the number of integers between 1 and 60 that are relatively prime to 60? I know that the answer is 16, but how do I go about finding the relative primes using a quick process?
$\endgroup$ 14 Answers
$\begingroup$You can use the Euler's totient, see for how it works. By the way, the answer is 16, not 15 (if you include 1).
If moreover you want to know who are those numbers, I guess you should list all the primes between 1 and 60 that does not appear in the factorisation of 60 ; then all the numbers you are looking for are made from those primes.
$\endgroup$ 2 $\begingroup$Erastothenes's sieve. The number of integers relatively prime to $60$ is equal to $\varphi(60)=\varphi(2^2)\,\varphi(3)\,\varphi(5)=16$. Here is the list: $$\bigl\{1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59\bigr\}.$$
$\endgroup$ 2 $\begingroup$Possibly the principle of inclusion-exclusion (PIE) is asked for here as this usually shows up when the Euler totient is computed. For $n$ having three prime divisors $p,q,r$ the corresponding Hasse diagram consists of nodes for all subsets $Q\subseteq \{p,q,r\}$ representing multiples of $\prod_{m\in Q} m$ less than or equal to $n$ with the empty product having value one and inclusion of the node $P$ in $Q$ if $Q\subseteq P$. Assigning weight one to the top node that corresponds to $\{\}$ and for the other nodes $Q$ the weight that makes the weights of the subset spanned by the $Q$ and the top node sum to zero yields $$n-n\sum_{\{p'\}\subseteq \{p,q,r\}}\frac{1}{p'}+n\sum_{\{p',q'\}\subseteq \{p,q,r\}}\frac{1}{p'q'}-n\sum_{\{p',q',r'\}\subseteq \{p,q,r\}}\frac{1}{p'q'r'}$$ which is $$n\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\left(1-\frac{1}{r}\right).$$
With $n=60$ this gives $$60\times\frac{1}{2}\times\frac{2}{3}\times\frac{4}{5} = 16.$$
$\endgroup$ $\begingroup$You can just use Euler's totient function. Given a prime $p$, $\phi(p^\alpha) = (p - 1)p^{\alpha - 1}$. The function is multiplicative, so $\phi(p^\alpha q^\beta) = \phi(p^\alpha) \phi(q^\beta)$.
Since $60 = 2^2 \times 3 \times 5$, you calculate $$\phi(60) = \phi(4) \phi(3) \phi(5) = 2 \times 2 \times 4 = 16.$$
To verify this answer, let's count up the primes from 7 to 59, and throw in there the odd composite numbers not divisible by 3 or 5, to get: 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59; this is a list of 16 integers.
I suppose either way is a quick enough process for small numbers. But if the numbers get just a little bit bigger, Euler's totient function is much faster: try for example to count up the integers between 1 and 5168743489 that are relatively prime to 5168743489.
$\endgroup$
