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:
-
$m=2 \times 3 \times 5=30$,
-
$m=2\times 3 \times 7=42$,
-
$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.
Best Answer
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.