My semester tests are coming up and as I was looking through past papers I came across this question. I was missing a lot during the beginning of the year and this was no doubt covered during my absence. If someone could run quickly through the theory and methods on this topic it would be hugely appreciated. Thank you. (Apologies if the tags aren't accurate, I wasn't even sure on them!)
The enciphered message AEF was produced by applying the enciphering function $$f_E:\Bbb Z_{26}\to\Bbb Z_{26}:x \mapsto 11x + 4$$ to single letter message units over the alphabet $A = 0,B = 1,\ldots,Z = 25$.
(i) Find the inverse of $11$ modulo $26$.
(ii) Determine the corresponding deciphering function.
(iii) Decipher the message.
The inverse of $11$ modulo $26$ is the integer $n\in\{0,\ldots,25\}$ such that $11n\equiv 1\pmod{26}$, or, if you prefer, $11n\bmod{26}=1$. There are theoretically more elegant ways to find $n$, but these numbers are small enough that brute force works fine. We want a multiple of $11$ that’s $1$ more than a multiple of $26$. The numbers that are $1$ more than the first few multiples of $26$ are $27,53,79,105,131,157,183,209$, and $209=11\cdot19$. Thus, the inverse of $11$ modulo $26$ is $19$.
Now suppose that we have a ciphertext number $y$. It comes from a plaintext number $x$ by the transformation $f_E$: $f_E(x)=y$. In this case that means that $y=(11x+4)\bmod{26}$. In other words, $y\equiv 11x+4\pmod{26}$, and $x,y\in\{0,\ldots,25\}$. Given $y$, you want to solve for $x$. Clearly $y-4\equiv 11x\pmod{26}$. Now multiply both sides by the inverse of $11$:
$$19(y-4)\equiv 19(11x)\equiv x\!\!\!\pmod{26}\;.$$
Thus, $$x=(19y-76)\bmod{26}=(19y+2)\bmod{26}\;,$$ since $76\bmod{26}=-2$.
The ciphertext AEF corresponds to the sequence $0,4,5$. Applying the transformation
$$f_D:\Bbb Z_{26}\to\Bbb Z_{26}:x\mapsto 19x+2\;,$$
we get the sequence $2,(19\cdot4+2)\bmod{26}=78\bmod{26}=0,(19\cdot5+2)\bmod{26}=19$, which corresponds to the plaintext CAT.