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

How can I prove the existence of a number c such that $\displaystyle 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