Statement Lemma For there exists where such that (mod ) if and only if . Proof Let the greatest common divisor be , so and where . Therefore consider the following modular arithmetic As has an inverse consider You can't use 'macro parameter character #' in math mode\overline{N} = \overline{N} \cdot 1 = \overline{N} \cdot x \cdot x^{-1} = 0 \cdot x^{-1} = 0 \ (mod \ N).$$ Therefore $\overline{N} = N$ and $gcd(x, N) = 1$. ## $\Leftarrow$ Consider the set of numbers $S = \{ i \cdot x \ mod \ N \vert 0 \leq i < N\}$. We know $\vert S \vert = N$ and for $s \in S$ we have $0 \leq s < N$. Suppose $$ i \cdot x = j \cdot x \ (mod \ N).$$ for $0 \leq i \leq j < N$. This gives us $$ (j - i) \cdot x = 0 \ (mod \ N).$$ Set $j-i := k$ where $0 \leq k < N$ now we have $k \cdot x = c \cdot N$. However as $gcd(x, N) = 1$ we have $N \vert k \cdot x$ giving $N \vert k$ making $k = 0$. Therefore all of $S$ are unique, so $1 \in S$ and we have a multiplicative inverse.