How do you find the inverse of $17x + 2$, to decode?

Question

Let's say I'm trying to encode "hi". "h" is $7$ and "i" is $8$. To encode it you do $17(7) + 2 = 119 \pmod {26} = 15$ which is "p", $17(8) + 2 = 138 \pmod {26} = 8$ which is "i".

Thus "hi" becomes "pi".

When I try to find the inverse it comes up as $\dfrac{x-2}{17}$, but let's say I'm trying to decode "pi". "p" is $15$ and "i" is $8$.

$\dfrac{15 - 2}{17} = 0.76 \pmod {26} = ? \\ \dfrac{8-2}{17} = 0.85 \pmod {26} = ?$

I't doesn't make sense. "pi" is supposed to go back to being "hi".

Answer 1

First, compute $\gcd(17,26)$ by Euclidean algorithm. $$9 = 26-17\quad\to\quad 8 = 17-9\quad\to\quad 1 = 9-8$$

Next, reverse the steps above and express $1$ as a linear combination of $17$ and $26$. $$1 = 9 - 8 = 9 - (17-9) = -1\times 17 + 2\times 9 = -1\times 17 + 2\times(26-17) = 2\times 26 -3\times 17 $$ Taking $\pmod{26}$ on both sides, we get $$-3\times 17 \equiv 1\pmod{26}\quad\implies\quad 23\times 17\equiv 1 \pmod{26}$$ This means $17$ is invertible in modulus $26$ arithmetic with inverse $23$.

For "pi" = $(17, 8)$, when we apply the reverse operations, one get

$$ \begin{array}{cccl} \textrm{p} = 17 & \leadsto & 17^{-1} \times (17-2) = 23\times (17-2) = 345 \equiv 7 \pmod {26} &\leadsto \textrm{h} \\ \textrm{i} = 8 & \leadsto & 17^{-1} \times (8-2) = 23\times (8-2) = 138 \equiv 8 \pmod {26} &\leadsto \textrm{i} \end{array} $$ Please note that the $17^{-1}$ above stands for inverse of $17$ in the modulus 26 arithmetic, not the rational number $\frac{1}{17}$.

Answer 2

Fill a map of the direct transform $(k,(17k+2)\bmod26)$ for $k\in[0,25]$, and sort it on the second number.

Answer 3

Saying that "x" is the multiplicative inverse of 17, modulo 26, means that 17x= 1 (mod 26) which, in turn, means that 17x= 26k+ 1 for some integer k. That is the same as the "Diophantine" equation, 17x- 26k= 1. Now, 17 divides into 26 once with remainder 9: 26- 17= 9. 9 divides into 17 once with remainder 8: 17- 9= 8. Finally, 8 divides into 9 with remainder 1: 9- 8= 1. Replacing that 8 by 17- 9, 9- (17- 9)= 2(9)- 17= 1. Replacing that 9 by 26- 17, 2(26- 17)- 17= 2(26)- 3(17)= 1. So one solution is x= 3, k= 2. So 1/17= 3 (mod 26)- 3*17= 51= 2(26)+ 1. The multiplicative inverse of 17, modulo 26, is 3. From that, (15- 2)/17= 13*3= 39= 26+ 19= 13 (mod 26). And (8- 2)/17= 6*3= 18 (mod 26).