Chinese remainder theorem and order

Question

How do I find out which elements of the monoid (Z/161Z, *, 1) are not invertable? I'm trying to find the group of units but I can't really grasp which elements are invertible and which aren't.

Answer 1

We have $161=7\cdot 23$. Everybody is invertible except multiples of $7$ or $23$.

Added: Note that a multiple $7k$ of $7$ cannot be invertible, for it is a zero-divisor: $(7k)(23)\equiv 0\pmod{161}$. The same applies to multiples of $23$.

To show that the others are invertible, suppose that $a$ is relatively prime to $161$. By Bezout's "identity," there are integers $x$ and $y$ such that $ax+161y=1$. It follows that $x$ (properly speaking, its equivalence class) is the inverse of (the equivalence class of) $a$.

If instead you want to use the Chinese Remainder Theorem, use the fact that any $a$ not divisible by $7$ has an inverse $s$ modulo $7$, and any $a$ not divisible by $23$ has an inverse $t$ modulo $23$. Let $x$ be the solution of the system of congruences $x\equiv s\pmod{7}$, $x\equiv t\pmod{23}$. Then $ax\equiv 1\pmod{161}$.