Recipe

Decide whether a is a unit mod n by direct search

Use when: you're given one specific residue $a$ mod $n$ and need to know whether it has a multiplicative inverse, before the gcd shortcut is available

Goal: a decision, unit or not a unit, and if it is, the actual inverse $b$

Taught in Units modulo n and the group U(n)

Quick recipe

List the products of a with every nonzero residue
Read the result off the list
Verify the inverse you found

1
Compute $a\times 1, a\times 2, \ldots, a\times(n-1)$ , each reduced mod $n$ , in order. Stop early the moment you spot either a $1$ or a repeated output.

Example

For $a=5$ , $n=9$ : $5\times1=5$ , then $5\times2=10\equiv1$ . The list already hit $1$ at $b=2$ , so there's no need to compute $b=3,\ldots,8$ .

Why: an inverse for $a$ , if one exists, must show up somewhere among these $n-1$ products, since $b$ itself is always one of the nonzero residues.
2
Look at what stopped the search in Step 1: whether it was a $1$ , or a repeated output before $1$ ever appeared.

Example

For $a=6$ , $n=9$ : $6\times1=6$ , $6\times2=12\equiv3$ , $6\times3=18\equiv0$ , $6\times4=24\equiv6$ . Inputs $1$ and $4$ both land on $6$ .
- $1$ appears among the outputs — $a$ is a unit, and the matching $b$ is its inverse.
- two different inputs give the same output before $1$ ever appears — $a$ is not a unit; stop, no need to finish the list.
⚡ Shortcut

Stopping the moment a repeat turns up is faster than computing every remaining product and comparing afterward. One genuine collision already proves $a$ isn't a unit.

Why: multiplying by $a$ mod $n$ either hits every nonzero residue exactly once, when $a$ is a unit, or repeats an output before it can, since there are only $n-1$ possible outputs for $n-1$ inputs.
3
Multiply $a$ by the $b$ you identified and confirm the product actually reduces to $1 \bmod n$ , rather than trusting the scan alone.

Example

$a=5$ , $b=2$ , $n=9$ : $5\times2=10$ , and $10 \bmod 9 = 1$ . The inverse checks out.

Why: a single arithmetic slip anywhere in the scan can produce a wrong $b$ , and this check catches it before it gets used anywhere else.

Common mistakes

Testing $a\times0$ or counting $0$ among the candidates -- $0$ is never part of the search, since $a\times0\equiv0\neq1$ always.
Treating one failed guess as proof $a$ isn't a unit, instead of continuing the search or finding a genuine collision.
Confusing "two outputs in the list happen to match" with an actual collision -- a collision needs two different inputs $b$ , not the same input computed twice.
Assuming every nonzero residue mod $n$ must be a unit, the way every nonzero real number has a reciprocal.