Modular Arithmetic - pairs of additive inverse pairs and multiplicative inverse pairs

The extended Euclidean algorithm is probably your best tool for anything but obvious multiplicative inverses. For simple inverses it can be useful to get comfortable with using negative congruences too, so $13\equiv -4 \bmod 17 $ and since $4^2\equiv -1$ then $4\cdot -4 \equiv 1 \bmod 17$.

To illustrate the extended Euclidean algorithm I'll use your example of finding $321^{-1} \bmod 56789$ (although not $56709$, since then they have a common factor of $3$). This proceeds effectively by finding a series of equations satisfying $n = 56789s +321t$, starting with $n = 56789$ and $n=321$ and proceeding to smaller values of $n$, until - if possible - $n=1$.

$\begin{array}{c|c} n & s & t & q \\ \hline 56789 & 1 & 0 & \\ 321 & 0 & 1 & 176 \\ 293 & 1 & -176 & 1 \\ 28 & -1 & 177 & 10 \\ 13 & 11 & -1946 & 2 \\ 2 & -23 & 4069 & 6 \\ 1 & 149 & -26360 & \\ \end{array}$

$q$ represents the multiplier to get a close match for the $n$ values of the previous two equations, giving the best reduction in $n$ for the next line.

The final equation here says that $1 = 56789\cdot 149 + 321\cdot(-26360)$. This of course means that $ 321\cdot(-26360) \equiv 1 \bmod 56789$ or, converting to a positive congruence, $321^{-1} \equiv 30429 \bmod 56789$.

The same process for finding $13^{-1} \bmod 17$ works also of course:

$\begin{array}{c|c} n & s & t & q \\ \hline 17 & 1 & 0 & \\ 13 & 0 & 1 & 1 \\ 4 & 1 & -1 & 3 \\ 1 & -3 & \color{red}{4} & \\ \end{array}$

For finding a full set of multiplicative inverses, we do have the advantage of generally only having to find less than half of them. Your listing of $\Bbb Z_{28}^\times$ includes some numbers that should not be there, since they do not have inverses - all those numbers which share a factor with $28$. The correct listing then is $\Bbb Z_{28}^\times = \{1,3,5,9,11,13,15,17,19,23,25,27\}$. $1$ is the identity already and $-1\equiv 27\bmod 28$ is self-inverse (always true for $1$ less than the modulus). Then we can look for multiples of the small numbers either side of the low multiples of $28$ (all equivalences $\bmod 28$):

$3\cdot 9 =27\equiv -1 \implies 3^{-1}\equiv -9 \equiv 19$
$5\cdot 11 =55\equiv -1 \implies 5^{-1}\equiv -11 \equiv 17$
from $3$'s result $9^{-1}\equiv -3\equiv 25$
from $5$'s result $11^{-1}\equiv -5\equiv 23$
$13\cdot 15 = (14-1)(14+1) \equiv -1 \implies 13^{-1}\equiv -15\equiv 13$
and similarly $15^{-1}\equiv -13\equiv 15$

with the other results being the other half of established inverse pairs, giving the full result:

$\{(1), (3,19), (5,17), (9,25), (11,23), (13), (15), (27)\}$

single items being self-inverse.

Multiplicative inverses are pairs $(a,b)$ where $a \cdot b = 1 \text{ mod m}$. $2 \cdot 26 \text{ mod m }$ isn't $1$ but $24$.

Multiplicative inverses are thus:

Prelude> [(x,y)|x<-[1..28],y<-[1..28],x*y `mod` 28 == 1] [(1,1),(3,19),(5,17),(9,25),(11,23),(13,13),(15,15),(17,5),(19,3),(23,11),(25,9),(27,27)] 

If $$s \cdot r = 1$$ then $$(m-r)\cdot(m-s) = 1$$ which means that if you have a pair of multiplicative inverses you get another one for free.

$$(m-r)\cdot(m-s) = m\cdot m -rm -sm +rs = rs = 1$$

It's obvious that $1$ is always a self-inverse because $1 \cdot 1 = 1$. This also means that $m-1$ is necessarily a self-inverse. If $(3,19)$ are inverses then $(28-3,28-19) = (25,9)$ thus if $(3,19)$ is a pair of inverses then $(25,9)$ must be a pair of multiplicative inverses as well.