Defining the Groups:
- $G = \{c \in \{1, 2, \ldots, n-1\} \mid \gcd(c,n) = 1\}$ represents the group of units mod $n$. These are the integers in the range $1$ to $n-1$ that are coprime to $n$.
- $H = \{c \in G \mid \text{ord}(c) \text{ is odd}\}$ represents the subset of elements in $G$ whose multiplicative order modulo $n$ is odd.
Proving that H is a Subgroup of G:
Attempt
For H to be a subgroup of G, it must satisfy the following properties:
- H is non-empty.
- Closure: For any two elements x and y in H, the result of the operation x * y is also in H.
- Associativity: The operation * is associative on H.
- Identity Element: The identity element of G is also in H.
- Inverse Element: For each element x in H, the inverse x⁻¹ (in G) is also in H.
Proof:
- H is closed under inversion.
- Let $k=ord(c)$ it implise $c^k\equiv 1 \mod n \to (c^k)^{-1}\equiv 1 \to (c^{-1})^{k}\equiv 1 \to c^{-1} \in H$
- Identity element 1 exist.
The first try on $H$ is closed under multiplication:
- Suppose $a$ and $b$ are two elements in $H$. This means $\text{ord}(a)$ and $\text{ord}(b)$ are odd.
- Now, consider the element $ab$. We want to show that $\text{ord}(ab)$ is odd.
- Let $\text{ord}(a)=2c+1$, $\text{ord}(b)=2d+1$, WLOG let 2c+1 < 2d+1, then we have $\mod n: a^{2c+1} \equiv 1, b^{2d+1} \equiv 1 \to a^{2c+1} b^{2d+1} \equiv 1 \to (ab)^{2c+1} b^{2(d-c)} \equiv 1$.
The second try with proof by contradiction:
- If $\text{ord}(ab)$ were even, then we'd have $(ab)^{2k} \equiv 1 \mod n$, which implies $a^{2k}b^{2k} \equiv 1 \mod n$.