You can try to find instead the number of numbers $1 \leq x \leq m$ which are relatively prime to $n$. Lets denote $d(m,n)$ this number. Then your answer is $\phi(n)- d(m,n)$.
If $p_1,..,p_k$ are all the primes dividing $n$, a simple inclusion-exclusion calculation tells us what $m-d(m,n)$ (namely the numbers which are not relatively prime to n) is:
There are $\left\lfloor \frac{m}{p_i} \right\rfloor$ multiples of $p_i$, there are $\left\lfloor \frac{m}{p_ip_j} \right\rfloor$ multiples of $p_i p_j$ and so on. Thus
$m-d(m,n)= \sum_{i=1}^k \left\lfloor \frac{m}{\,p_i\,} \right\rfloor -\sum_{ 1 \leq i < j \leq k} \left\lfloor \frac{m}{p_ip_j} \right\rfloor+\sum_{ 1 \leq i < j< l \leq k} \left\lfloor \frac{m}{p_ip_jp_k} \right\rfloor-\ldots+(-1)^{k-1} \left\lfloor \frac{m}{p_1p_2....p_k} \right\rfloor$
Thus, unless I made a mistake, your number is
$\phi(n)-m+\sum_{i=1}^k \left\lfloor \frac{m}{p_i} \right\rfloor -\sum_{ 1 \leq i < j \leq k} \left\lfloor \frac{m}{p_ip_j} \right\rfloor+\sum_{ 1 \leq i < j< l \leq k} \left\lfloor \frac{m}{p_ip_jp_k} \right\rfloor-\ldots+(-1)^{k-1} \left\lfloor \frac{m}{p_1p_2....p_k} \right\rfloor$
P.S. I am not sure if the sum is calculable in reasonable time, there are $2^k$ terms where $k$ is the number of prime factors of $n$. $k$ is typically smaller than $\log_2(n)$ but I am not sure if it is always smaller than $\log(\log(n))$.
Also, it is improbable that the sum can be simplified further, due to the integer part. The easy case is when $m$ has exactly the same divisors as $n$, and then it can be simplified to $\phi(n)-\phi(m)$, but in this case this result can be obtained easily directly.