iff there exists an integer d such that ac + nd = 1. But it is known that the set of linear combinations of two numbers coincides with the set of multiples of their GCD. (The GCD can be expressed as a linear combination through the Euclidean algorithm, and every linear combination is a multiple of the GCD.) Thus, has a multiplicative inverse mod n iff GCD(a, n) = 1.