Zn* is a group

Dependencies:

1. Existence of Modular Inverse
2. ab is coprime to x iff a and b are coprime to x

$\mathbb{Z}_n^*$ is a group under multiplication mod $n$.

Proof

• Closure: $$a, b \in \mathbb{Z}_n^* \Rightarrow \gcd(a, n) = \gcd(b, n) = 1 \Rightarrow \gcd(ab, n) = 1 \Rightarrow ab \in \mathbb{Z}_n^* $$

• Associativity: Multiplication modulo $n$ is associative.

• Identity: 1 is identity.

• Inverse: $a \in \mathbb{Z}_n^* \Rightarrow \gcd(a, n) = 1 \Rightarrow$ inverse of $a$ modulo $n$ exists.

Therefore, $\mathbb{Z}_n^*$ is a group.

Dependency for:

1. Euler's Theorem Used in proof

Info:

• Depth: 4
• Number of transitive dependencies: 6

Transitive dependencies:

1. Every number has a prime factorization
2. Integer Division Theorem
3. GCD is the smallest Linear Combination
4. Euclid's lemma
5. ab is coprime to x iff a and b are coprime to x
6. Existence of Modular Inverse