I am taking a Cryptography class and we are working on modular arithmetic. I am still unsure on how to find pairs of additive inverse pairs and multiplicative inverse pairs. I've seen some videos and attempted to read about doing so but I find myself confused on what exactly I'm looking for. I've learned about the GCD, euclidean algorithm, but i just can't seem to piece it all together. Any help would be much appreciated. Thanks!
Example:
13 mod 17
How I got this:
For the additive inverse, I take the number given (13) and then find the number that would add up to n (n=17), in this case it is 4.
For the multiplicative inverse, I take the number given (13) and then add n to it(n=17), and then I find a number that multiples with 13 to be congruent to 1.
I picture a clock with n numbers around it. Im worried when it comes to a much bigger number such as 321^-1 mod 56709.
additive inverse:(13,4)
multiplicative inverse: a x b = 1(mod 17)
13 x 4 = 1(mod 17)
I'm working on another example:
list all additive inverse pairs and multiplicative inverse pairs of the sets Z28 and Z28*.
So far i have this:
Integers in the set:
Z28 = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27}
Z28* = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27}
Additive Inverse Pairs:
Z28 = (0,0),(1,27),(2,26),(3,25),(4,24),(5,23),(6,22),(7,21),(8,20),(9,19),(10,18),(11,17),(12,16),(13,15),(14,14)
Z28* = (1,27),(2,26),(3,25),(4,24),(5,23),(6,22),(7,21),(8,20),(9,19),(10,18),(11,17),(12,16),(13,15),(14,14)
as for the multiplicative inverse pairs, its taking me a while to check each one. Another question is, is there a faster way to find all inverse pairs of a set?
Best Answer
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.