Affine Cipher finding the decryption map

Question

Given two letters of the plaintext 'ZP' corresponding to the ciphertext 'AE' respectively, I have found the key to be (a,b)=(10,10) (modulo 26).

Therefore the decryption map $D(x)=a^{-1}(x-a)\bmod26$ I obtain here is $D(x)=10^{-1}(x-10) \bmod26$. However, $10^{-1}\bmod26$ does not exist so how am I able to find this? Have I got the key wrong? I know $(23,23)$ also works but i dont know how to find that key with my working.

This is my working:

$25a+b\equiv0 \pmod{26}$, $15a+b\equiv4 \pmod{26}$

where $(a,b)$ are the two elements of the key, and $Z,A,P,E$ correspond to the numbers $25,0,15,4$ using the standard translation of the alphabet to numbers, starting with $A=0$.

Then using simultaneous equations I get:

$10a\equiv-4\pmod{26}$ which can be written as $10a\equiv22\pmod{26}$ as $-4\equiv22\pmod{26}$.

Then dividing by $2$ you get $5a\equiv11\pmod{13}$ so $a\equiv11\cdot5^{-1}\pmod{13}$ then by using the extended euclidean algorithm you can calculate the inverse of $5\bmod 26$ which is $-5\pmod{13}$ or $8\pmod{13}$.

Therefore $a\equiv11\cdot 8 \pmod{13}$, $a\equiv88\pmod{13}$ and so you get $a\equiv10\pmod{13}$.

Therefore $a=10$ and by plugging $a=10$ into $25a+b\equiv0\pmod{26}$,

I get $250+b\equiv0\pmod{26}$ and so $b\equiv-250\pmod{26}$ which then gives $b=10$ and so $(a,b)=(10,10)$.

Answer 1

We indeed know that

1. $25a + b \equiv 0 \bmod 26$

from 'Z' mapping to 'A' and

2. $15 a + b \equiv 4 \bmod 26$

from 'P' mapping to 'E' under $E(x) = ax + b \bmod 26$.

subtracting 2 from 1, we get $$10a \equiv -4 \equiv 22 \bmod 26$$

Subtracting 15 times (1) from 25 times (1) the $a$'s cancel and we get

$$10b \equiv 100 \equiv 22 \bmod 26$$ as well.

So we just have to solve $10x \equiv 22 \bmod 26$, and check the answer.

If I'm lazy I open my terminal and in python one can type:

for a in xrange(26): if 10*a % 26 == 22: print a (with proper formatting of course)

and we get 10 and 23 as answers. So we have 4 options to check against the original equations, and both $(23,23)$ and $(10,10)$ work, it turns out. with the former we have a proper decryption function, as $23^{-1} \bmod 26 \equiv 17$. The other option has no decryption function, as $\gcd(10, 26) \neq 1$ .So $(23, 23)$ is actually correct and $D(x) = 17(x-23) \bmod 26$.

For a more mathematical solution to $10x \equiv 22 \bmod 26$, we can follow the algorithm described in these notes (theorem 2.7).

We compute $d = \gcd(10,26) = 2$ and we write (extended Euclidean)

$$2 \cdot 26 -5 \cdot 10 = 2$$

Multiplying this with $11 = \frac{22}{2}$ we get

$$2 \cdot 26 \cdot 11 -5 \cdot 10 \cdot 11= 22$$ which shows (look at it modulo 26) that

$ x =-55= -5 \cdot 11$ is a particular solution to our original equation. Then we add multiples of 13 ($\frac{26}{2}$) for all other solutions, so we get $-55 \equiv -3 \equiv 23 \bmod 26$ is the one and $-3 + 13 = 10$ is the other one, confirming the python script answer.