# Math Help - Existence of a multiplicative inverse

1. ## Existence of a multiplicative inverse

A quick question this time. I have a number n and number a. Both positive integers such that $1 \leq a \leq n$.

How can I prove the existence of a number c such that $ac \equiv 1 \text{ (mod n)}$

Obviously I can't use the Euclidean algorithm since I have no specific relation between a and n. How can I prove existence of c? (Or can't I?)

Thanks!

-Dan

2. ## Re: Existence of a multiplicative inverse

$ac\equiv 1\pmod{n}$ 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, $a$ has a multiplicative inverse mod n iff GCD(a, n) = 1.

3. ## Re: Existence of a multiplicative inverse

Originally Posted by emakarov
$ac\equiv 1\pmod{n}$ 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, $a$ has a multiplicative inverse mod n iff GCD(a, n) = 1.
(sighs) You know, I worked that problem for more than 2 hours. Then I figured it out about 15 minutes later as I was leaving my house. Grrrrrr...

Thanks for the help!

-Dan