<s>[INST] How to solve for positive relatively prime numbers? When finding the relative prime for large numbers like 360 (that has a prime factorization with multiples of the same prime factor), how would it be solved?
ie. How many numbers between 1 and 360 are relatively prime to 360?
I would think either 


*

*N = 360 [prime factorization: 2, 2, 2, 5, 9]

*$N(A_1) = \frac{360}{2}$

*$N(A_2) = \frac{360}{5}$

*$N(A_3) = \frac{360}{9}$

*$N(A_1 \cup A_2) = ...$

*$N(A_1 \cup A_3) = ...$

*$N(A_2 \cup A_3) = ...$
...
or


*

*N = 360 [prime factorization: 2, 2, 2, 5, 9]

*$N(A_1) = \frac{360}{2}$

*$N(A_2) = \frac{360}{2}$

*$N(A_3) = \frac{360}{2}$

*$N(A_4) = \frac{360}{5}$

*$N(A_5) = \frac{360}{9}$

*$N(A_1 \cup A_2) = ...$
...
 [/INST] 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


*

*$360/2 = 180$ numbers up to $360$ are divisible by $2$.

*$360/3 = 120$ numbers up to $360$ are divisible by $3$.

*$360/5 = 72$ numbers up to $360$ are divisible by $5$.


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


*

*There are $360/6 = 60$ divisible by $2$ and $3$.

*There are $360/15 = 24$ divisible by $3$ and $5$.

*There are $360/10 = 36$ divisible by $2$ and $5$.


But we've overcounted how much we've overcounted! There are also numbers divisible by $2$, $3$, and $5$.


*

*There are $360/(2 \cdot 3 \cdot 5) =12$ numbers up to $360$ that are divisible by $2\cdot3\cdot5 = 30$.


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.
</s>