Without the extended Euclidean algorithm, how can you find or check a multiplicative inverse $x^{-1} \mod N$ by hand?

Question

Accepted Answer

Three hand methods: try multiples of $x$ until one is $\equiv 1 \mod N$, read the inverse off a multiplication table, or check a claimed inverse $y$ by computing $x \cdot y \mod N$.
The extended Euclidean algorithm computes inverses directly, but for small or given numbers these are faster:
1. Trial (Durchprobieren). Compute $x \cdot 1, x \cdot 2, x \cdot 3, \dots \mod N$ until the result is 1. For $15^{-1} \mod 26$:

$y$
1
2
3
4
5
6
7

$15 \cdot y \mod 26$
15
4
19
8
23
12
1

So $15^{-1} \equiv 7 \mod 26$.
2. Reading a multiplication table. In the table of $x \cdot y \mod N$, find the cell that holds 1 in row $x$; its column is $x^{-1}$. A row with no 1 means no inverse exists. For mod 15 this gives:

$x$
1
2
4
7
8
11
13
14

$x^{-1} \mod 15$
1
8
4
13
2
11
7
14

That is exactly $\varphi(15) = 2 \cdot 4 = 8$ inverses. The rows for 3, 5, 6, 9, 10 and 12 contain no 1, because those numbers share a factor with 15.
3. Checking a claim. Is $149 \equiv 125^{-1} \mod 192$? First, $\gcd(125, 192) = 1$ ($125 = 5^3$, $192 = 2^6 \cdot 3$), so an inverse exists. Then $125 \cdot 149 = 18\,625 = 97 \cdot 192 + 1 \equiv 1$, so yes. The neighbour 148 fails: $125 \cdot 148 \equiv 68 \mod 192$.
Patterns that save work:

Inverses come in pairs: $15^{-1} \equiv 7$ also gives $7^{-1} \equiv 15 \mod 26$
$1$ and $N - 1$ are always their own inverse, because $(N-1)^2 = N^2 - 2N + 1 \equiv 1 \mod N$. Others can be too: mod 15, both 4 and 11 are self-inverse
For a prime modulus $p$, every element except 0 has an inverse, and only $1$ and $p - 1$ are self-inverse

Go deeper:

Modular inverses (Khan Academy) — the trial method worked step by step, with a calculator to check by hand.