MHB Show the Units of Zn with modular multiplication are a group

[E01]

I am trying to do an exercise where I am showing that the set of all elements of $\Bbb{Z}_n$ that are coprime with n form a group under modular addition.

So far I have shown associativity, identity, and closure, but I'm having trouble showing the existence of an inverse. I know I can't use reciprocals and I can't find a way to prove that for $r \in U_n$ there exists some $t \in U_n$ such that $tr$ has a remainder of 1 when divided by n.

Any hints?

 

[Euge]

I am trying to do an exercise where I am showing that the set of all elements of $\Bbb{Z}_n$ that are coprime with n form a group under modular addition.

So far I have shown associativity, identity, and closure, but I'm having trouble showing the existence of an inverse. I know I can't use reciprocals and I can't find a way to prove that for $r \in U_n$ there exists some $t \in U_n$ such that $tr$ has a remainder of 1 when divided by n.

Any hints?

Hi E01,

Use the fact that $gcd(r,n) = 1$ if and only if there exist integers $s$ and $t$ such that $rs + nt = 1$.

 

[Deveno]

I am trying to do an exercise where I am showing that the set of all elements of $\Bbb{Z}_n$ that are coprime with n form a group under modular addition.

So far I have shown associativity, identity, and closure, but I'm having trouble showing the existence of an inverse. I know I can't use reciprocals and I can't find a way to prove that for $r \in U_n$ there exists some $t \in U_n$ such that $tr$ has a remainder of 1 when divided by n.

Any hints?

Hint #2: take Euge's equation mod $n$.