Ensure that for each number in specific space there is inverse

Question

Let say I want to find the Inverse number of some serial number. ( 9 digits number .. its can be an ID).
And let say we want to find the inverse in $\mathbb Z_{1000000123}$ ( for example )
How I can ensure that for each serial number \ ID there is an inverse.

• Its matter if its prime or not? ( the $\mathbb Z $ space )?
  

Any suggestions are welcomed.

Answer 1

You need the number you want to invert and the modulus to be relatively prime, which means to have greatest common divisor of $1$. You can check that with the Euclidean algorithm. Having the modulus a prime greater than the serial number is a way to make sure the GCD is $1$, but it is not required.