Coprime solutions to ax ≡ b (mod n )

Abstract. It is well known that a congruence ax ≡ b (mod n ) has a solution if and only if , and, if the condition is satisfied, the number of incongruent solutions equals . In 2010, Alomair, Clark and Poovendran proved that the congruence ax ≡ b (mod n ) has a solution coprime to n if and only if , as an auxiliary result playing a key role in a problem related to an electronic signature. In this paper we provide a concise proof of this result, together with a closed formula for the number of incongruent solutions coprime to n as well. Moreover, a bound is presented for the probability that, for randomly chosen , this congruence possesses at least one solution coprime to n .