Comment by misterrobot

"Division" i.e. multiplying by the multiplicative inverse doesn't require the modulus be prime; it just requires that the number you are finding the inverse of and the modulus are relatively prime.