Relative primes

Question

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?

Answer 1

You can use the Euler's totient, see http://en.wikipedia.org/wiki/Euler%27s_totient_function 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.

Answer 2

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\}.$$

Answer 3

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.$$

Answer 4

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.