Affine cipher : Why it is required to have GCD(a, m) equals to 1 In the Affine cipher, the key $k = (a, b)$ should have the following property, i.e. GCD of $a$ and the modulus should be 1:


  $\gcd (a, m) = 1$, where $m$ is the set of possible moduli


My question is, why it is required that $a$ should have the above property? What is the significance of this? And why is $b$ excluded from this condition?
OK, to understand this issue, let's first recap how the affine cipher is defined:

$$c=a\cdot x+b\bmod m$$

Note that the following holds: $a\cdot x+b=c\iff a\cdot x=c-b$, where you would calculate $-b$ as $m-b$ which is $&gt;0$ because $m&gt;b$ because otherwise you could reduce $b\bmod m$ further.

Ok, so on our way to decryption we now only need to get $x$ out of $a\cdot x=c'\bmod m$ (with $c'=c-b\bmod m$).

Now if $d=\gcd(a,m)&gt;1$ then this equation has either $0$ or $d$ solutions, neither being what you want from a decyption function (no plaintext recovery or uncertain plaintext recovery).

So this is why we make the restriction $\gcd(a,m)=1$, which will ensure that there is exactly one integer solution to $a\cdot x=c'\bmod m$ with $0\leq x&lt;m$.

If you want illustration of the lack of solutions, have a look at the modular multiplication table of for example 15. You will note for example that there is no $x$ such that $6\cdot x=5\bmod 15$ however, there are three $x$ such that $6\cdot x=3\bmod 15$ and note that $\gcd(15,6)=3&gt;1$.