The question is as follows:
Find all pairs of integer keys $(a, b)$ for affine ciphers for which
the encryption function $c = (ap + b) \bmod 26$ is the same as the
corresponding decryption function.
I'm trying to wrap my head around the answer provided:
If $x$ is the inverse of $a$ modulo 26, then the decryption function for the encryption function $c = (ap+b) \bmod 26$ is $p = x(c − b) \bmod 26 = (xc − xb) \bmod 26$. Clearly two different pairs $(a, b)$ cannot give the same encryption function, so we need to solve the system of congruences $x \equiv a \pmod{26}$ and $b \equiv −xb \pmod{26}$. Only 1 and −1 (which is the same as 25) are their own multiplicative inverses modulo 26 (this can be verified by asking a computer algebra system to compute all the inverses), so there are two cases. If $a = 1$, then the second congruence becomes $b \equiv −b \pmod{26}$, whose solutions are $b = 0$ and $b = 13$. This says that the identity function $c = p \bmod 26$ satisfies the given condition (although that was obvious and not very interesting), and so does $c = (p + 13) \mod 26$. If $a = −1$, then the second congruence becomes $b \equiv b \pmod{26}$, which is satisfied by all values of $b$. Therefore all encryption functions of the form $c = (−p + b) \bmod 26$ also have themselves as the corresponding decryption function. The answer to the question phrased in terms of pairs is $(1, 0)$, $(1, 13)$, and $(−1, b)$ (or, equivalently, $(25, b)$) for all $b$.
How do we get the congruences $x \equiv a \pmod{26}$ and $b \equiv −xb \pmod{26}$ from $(xc − xb) \mod 26$?
Best Answer
The function $p\longmapsto ap+b\bmod{26}$ has inverse $c\longmapsto \frac{1}{a}(c-b)\bmod{26}$; this is always the case (provided $\gcd(a,26)=1$, which is clearly assumed).
Here we want the two functions to be the same. So denoting as the answer does, the multiplicative inverse modulo $26$ of $a$ by $x$, we have that we want $$x(c-b) \equiv ac+b\pmod{26}$$ for all $c$.
This gives $$\text{for all }c,\quad xc -xb \equiv ac+b\pmod{26}.$$ We can take $c=0$ and conclude that we must have $-xb\equiv b\pmod{26}$. And then cancelling we get $xc\equiv ac\pmod{26}$, and since this must hold for all $c$, taking $c=1$ we get $x\equiv a\pmod{26}$.
So if the encryption function equals the decryption function, then we must have $b\equiv-xb\pmod{26}$ and $x\equiv a\pmod{26}$. Conversely, if $b\equiv -xb\pmod{26}$ and $x\equiv a\pmod{26}$, then the encryption function and the decryption functions are equal, since we have $$ ap+b\equiv xp-xb\equiv x(p-b)\pmod{26},$$ so the encryption function equals the decyrption function, because the function that sends the input $p$ to $ap+b\bmod 26$ (the encryption function) gives the same value as sending it to $x(c-b)\pmod{26}$ (the decryption function).
So we are trying to find number pairs $(a,b)$ such that for $x$ the multiplicative inverse of $a$ modulo $26$, we have $xb\equiv -b$ and $x\equiv a$ modulo $26$. This is how we got those two congruences. Not merely from $xc-xb\bmod 26$, but from this having to be the same as $ac+b\bmod{26}$ for all values of $c$.
At this point we have that we need an $a$ that is its own multiplicative inverse modulo $26$. The only two such values are $1\bmod 26$ and $25\bmod 26$ (the only values modulo $13$, a prime, are $1$ and $-1$; the only value modulo $2$ is $1$; so by the Chinese Remainder Theorem, the only values modulo $26$ are indeed $1$ and $-1$).
If $a=1$, then $x=1$ and the second congruence becomes $b\equiv -b\pmod{26}$. The only solution is $b=13\bmod 26$. So one pair is $(1,13)$.
If $a=-1$ then $x-=1$ and the second congruence becomes $b\equiv b\pmod{26}$. Any value of $b$ will work, so here we get all pairs of the form $(-1,b)$, $b=0,1,\ldots,25$; this is the solution given.