0
$\begingroup$

May you please verify I wrote this proof down correctly? I am practicing proof writing, and I hope to get better through your help! Many thanks :)

Theorem: The set $G_n$ of non-zero elements of $(Z_n,+,\times$ that are not $0$ divisors forms of a group under multiplication modulo $n$.

Proof:

We have to show closure, identity existence, and inverses for all elements, (associativity transcends from the Ring)

$a\in G_n$ iff $gcd(a,n)=1$ by our previous work in Ring theory ($a$ is not $0$ divisor iff $gcd(a,n)=1$).

Closure: We have to show $ab\in G_n$ for all $a,b\in G_n$. We have $gcd(a,n)=1$ and $gcd(b,n)=1$ which means $a,b$ have no common factors with $n$, which means their product have no common factors with $n$ either, so $gcd(ab,n)=1$, so $ab\in G_n$. (Do I have to prove that their product has no common factors? If so my proof will be at the bottom)

Identity: Show that $1\in G_n$. We have $gcd(1,n)=1$ so $1\in G_n$(for all $n\in N$),

Inverses: Show that $\forall a\in G_n$, there exists $b\in G_n$ such that $ab=1$. So lets $G_n=\{1,a_1,...,a_{n-1}\}$. We have proved closure, so if I were to multiply $G_n$ by a fixed $a_i$ with $1 \le i\le n-1$. Then the new elements $a_i1$ and $a_ia_j$ $1 \le j\le n-1$ obtained would be the same elements in different order, and would still be in the group, and all distinct, and none of them equal to $0$ as none of them are $0$ divisors shown above. Suppose they were not distinct, then $a_ia_j=a_ia_k$ for some $a_j\not=a_k$, but by left cancellation (made possible by the fact that there are no $0$ divisors in the group) $a_j=a_k$ contradiction. So all elements are distinct and non-zero. Since there $a_i1\not=1$ we have that there must be a certain $a_ia_j=1$, meaning $a_j$ is the inverse of $a_i$ and since these are arbitrary elements, it applies to all elements in $G_n$.

$\endgroup$
1
  • $\begingroup$ More usual notation: either $\;\left(\Bbb Z_n\right)^*\;$ or even $\;U(n) \;\;\text{or}\;\; U(\Bbb Z_n)\;$ ... $\endgroup$
    – DonAntonio
    Feb 15, 2018 at 11:45

1 Answer 1

1
$\begingroup$

Basically your proof is fine though slightly cumbersome. For the inverse it could be better to use

$$gcd(a,n)=1\implies\;\text{exist}\;x,y\in\Bbb Z\;\;s.t.\;\;xa+yn=1\implies xa\pmod n=1$$

and there you found that $\;x\pmod n\;$ is the multiplicative inverse of $\;a\;$ .

$\endgroup$
1
  • $\begingroup$ Simplification at it's finest, thank you very much! As for the notation, I am using Fraleigh's notation. $\endgroup$
    – Kam
    Feb 15, 2018 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.