Coprime with $n$ and their modular inverses in $\Bbb Z_n$

Question

Consider $P = \{p_1, \ldots,p_l\}$ the set of numbers coprime to $n$, and set $P^{-1} = \{p_j^{-1}\}$ of inverses in $\Bbb Z_n$, that means: $$ p_j^{-1}p_j \equiv 1 \pmod n $$ I have proved that $P = P^{-1}$ as sets. Suppose that exists $q \in P^{-1}$ which is inverse to some $p_j \in P$: $$qp_j \equiv 1$$ such that $q$ isn't coprime with $n$, then exists non-zero $k \in \Bbb Z_n$ for which we have: $$ qk \equiv 0$$ that implies $$k \equiv (p_jq)k = p_jqk = p_j(qk) \equiv 0 $$ Contradiction.

I am interested in more interesting proof of this fact, may be something theoretical-set, combinatorial, etc...

Answer 1

If $q p \equiv 1 \pmod n$ then $qp =1+nk$, so $qp-nk=1$. But $\gcd(q,n)$ divides every lineal combination of $q$ and $n$, so $\gcd(q,n) | qp-nk=1 $.

Answer 2

The set $P$ is a group under multiplication (with reduction modulo $n$). If $G$ is a group, then the map $g\mapsto g^{-1}$ is inverse of itself, so it is a bijection.

Answer 3

First,your set P must contain all number that coprime to n in$\mathbb{Z} _n$(otherwise you can't proof q is contained in P from q is coprime to n)

if $\left( a,n \right) =1$,we konw that $a^{\varphi \left( n \right) -1}=1$,and we konw Congruence Expression of First Degree $ax\equiv 1\left( \mod n \right),\left( a,n \right) =1$ have exactly one solution.so we can get the $a^{-1}=a^{\varphi \left( n \right) -2}$,and$a^{\varphi \left( n \right) -2}\in P$,so $P^{-1}\subseteq P$

And we konw that if $a\ne b$,then $a^{-1}\ne b^{-1}$,so $|P^{-1}|=|P|$,then$P^{-1}=P$