# Existence of Modular Inverse

## Dependencies:

- GCD is the smallest Linear Combination Used in proof

$(\exists x, ax \equiv 1 \pmod{n}) \iff \gcd(a, n) = 1$

## Proof

$$ \gcd(a, n) = 1 \iff \exists x \exists y, ax + ny = 1 \iff \exists x, ax \equiv 1 \pmod{n} $$

## Dependency for:

## Info:

- Depth: 2
- Number of transitive dependencies: 2