Proof relatively prime numbers

Question

Let $p,q,r$ be three distinct prime numbers and $m = p\times q\times r$. How many of the numbers {$1,2,...,m$} are relatively prime to $m$?

My attempt:

1. $m=2 \times 3 \times 5=30$,

2. $m=2\times 3 \times 7=42$,

3. $m=3\times 5\times 7=105$,

and I see the pattern that relatively prime numbers to $m$ are prime numbers(and their powers) except {$p,q,r$}. Prime factorization of $m$ is $p\times q\times r$ and I can maybe argue that $m$ cannot be divided by any other prime number.

But how do I prove this more formally ? I can't see any formal way to do it.

Answer 1

You can clearly see it from Euler's totient function.

Answer 2

The solution to this is given by Euler's totient function, which can be computed explicitly using Euler's product formula (see: here)

If this machinery seems too complex, since the number you're dealing with only has three primes in its prime factorization, you could consider a "Brute Force" approach:

Let $A^{\ell}_{m} :={\{x : x=c\cdot \ell,\ c\in \mathbb{N}, x\leq m}\}$

Note that the sets $A^{p}_{m},\ A^{q}_{m},\ A^{r}_{m},\ A^{pq}_{m},\ A^{pr}_{m},\ A^{qr}_{m}$ contain all natural numbers that are NOT relatively prime to $m$.

So how many of the numbers ${\{1,2,...,m}\}$ are relatively prime to $m$? $$m-\vert A^{p}_{m} \cup A^{q}_{m}\cup A^{r}_{m}\cup A^{pq}_{m}\cup A^{pr}_{m}\cup A^{qr}_{m} \vert $$

Note that there is some overlap between these sets, but the size of the union can easily be determined using inclusion-exclusion.

Answer 3

This is a simple counting problem disguised as number theory. Among the numbers $1,2,\ldots,m$, it is easy to count the number of multiples of $p$, those which are multiples of $q$, and those which are multiples of $r$. Now we need to exclude numbers which we counted twice, and add back those we excluded too many times. This idea is known as the Principle of Inclusion and Exclusion and is a well-known method of counting. This can be applied to your case to find the answer, and can also be generalised to an arbitrary number of primes.