Validate my proof of $U(n) = \lbrace k : (k, n) = 1 \text{ and } 0 < k < n \rbrace$ is closed under modular multiplication

86 Views Asked by At

Let $A, B \in U(n)$ for $n \in \mathbb N^+$. Then we need to show that (ordinary) multiplication of $A, B$ satisfies the following,

$$(AB, n) = 1$$

which can be done using the Bézout's lemma for $A, B$ respectively, then multiplying and manipulating the result.

$$Ax + ny = 1,$$ $$Bx' + ny' = 1,$$

For some $x, x', y, y' \in \mathbb Z$.

$$(Ax + ny)(Bx'+ny') = 1$$ $$\Longrightarrow$$ $$[AB]u +[n]v = 1$$

which shows us that $AB$ and $n$ are relatively prime. For sake of readability, i didn't write the cumbersome calculations but instead of it used $u$ and $v$ as placeholders.

If we apply the division theorem to $AB$ with $n$ we will obtain the remainder $R$ which is same as the modular multiplication of $A$ and $B$. Respectively by the division theorem and Euclid's method we know that,

$$0 < R < n,$$ $$(AB, n) = (n, R) = (R, n) = 1.$$

So it has to be true that $R \in U(n)$, hence this finite group is closed under modular multiplication.

$\backsim$ QED $\backsim$