How to find a number of integral solutions (all $x$)

Question

If $A$ is between $[1..9000]$ $$A*X = 1 \pmod{9000}$$ All parameters are integers.

I have found some solutions: $$A = 6907, X = 43,$$ $$A = 7111, X = 991$$

But I don't know how to find all $x$.

I want to know how many of them exist.

Answer 1

By Euler`s Theorem, if $\gcd(X, A) = 1$, $X \equiv A^{\phi(9000) - 1} \pmod {9000}$, then $XA \equiv 1 \pmod {9000}$, were $\phi(n)$ is the Euler Totient Function.

Therefore the answer is as long as $A$ is coprime to $9000$, $X$ exists. Therefore there are $\phi(9000)$ number of $A$, or $2400$ of them.

Not the best answer, but it is short.