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 gcd(a,n)|b, and, if the condition is satisfied, the number of incongruent solutions equals gcd(a,n). In 2010, Alomair, Clark and Poovendran proved that the congruence ax = b (mod n) has a solution coprime to n if and only if gcd(a,n) = gcd(b,n), 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 integer a, b, this congruence possesses at least one solution coprime to n.