combinatoricselementary-set-theoryinclusion-exclusionprime numbers
How many positive integers less than or equal to $462$ are relatively prime to $462$?
My Approach
Well my approach is basically that we find $|A \cup B|$ where:
I just don't know how to calculate this so it is not an efficient method so please answer with a more efficient method. Thank you!
Edit 2: If you consider the analogous question for five digit numbers, then you will also find that the answer is $72$; so, perhaps someone can find a slick bijection between the two sets.
The technique for five digit numbers is relatively simple:
You need to avoid having $2$ and $4$ as adjacent; so, you can place them without constraints in $5(4) = 20$ places, but then subtract off the $8$ adjacent cases for $12$ in total.
Once $2$ and $4$ are placed, the $1$, $3$, and $5$ can be placed in any order among the three empty slots, i.e., $3! = 6$ ways, yielding $12 \cdot 6 = 72$ as the total.
Edit 1: Here is an AoPS link that also finds the answer to be 72. The underlying technique is to place the 2, 4, and 6 first; then, you figure out where the remaining digits can go. For those who do not wish to click through, here is an image of the text:
Brute force, in case others have craftier ways and want to check/verify; seventy two in total:
123456 143256 165234 165432 213456 214356 216534 216543 231456 231654 234156 234165 234516 234561 235416 235614 253416 254316 256134 256143 321456 321654 325416 325614 341256 341652 345216 345612 412356 413256 416523 416532 431256 431652 432156 432165 432516 432561 435216 435612 452316 453216 456123 456132 523416 543216 561234 561432 612345 612354 612534 612543 613254 613452 614325 614352 614523 614532 615234 615432 651234 651432 652134 652143 652314 652341 653214 653412 654123 654132 654312 654321
What primes do you need to worry about? The primes that divide $360$ are $2,3,5$, so you really want to find those numbers which are not divisible by $2, 3$, or $5$.
Now
But some numbers are divisible by both $2$ and $3$, or by $3$ and $5$, or $2$ and $5$. So we've overcounted. (This is an inclusion-exclusion argument in progress).
But we've overcounted how much we've overcounted! There are also numbers divisible by $2$, $3$, and $5$.
Thus in total there will be
$$ 360 - (180 + 120 + 72 - (60 + 24 + 36 - (12))) = 96.$$
In fact, this is one way of understanding the expression for $\varphi(n)$ given by $$ \varphi(n) = n\prod_{p \mid n} \left( 1 - \frac{1}{p} \right),$$ which encodes this inclusion-exclusion argument within it.
Best Answer
HINT: Euler's Totient function $\phi$ is multiplicative. In other words, if we have two positive integers $a$ and $b$ with $\gcd(a,b) = 1$, then $\phi(ab) = \phi(a)\phi(b)$. So, you can use prime factorization of $462$ to divide and conquer the problem.