Let n, x be positive integers. Prove that x has a multiplicative inverse modulo n if and only if gcd(n, x) = 1. (Hint: Remember an iff needs to be proven both directions. The gcd cannot be 0 or negative.)