Existence of Modular Inverse

Dependencies:

1. 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:

1. Chinese remainder theorem
2. Zn* is a group
3. Zp is a field

Info:

• Depth: 2
• Number of transitive dependencies: 2

Transitive dependencies:

1. Integer Division Theorem
2. GCD is the smallest Linear Combination