# 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?

• This is explained directly in the article you linked "The multiplicative inverse of a only exists if a and m are coprime". Essentially, you won't be able to decrypt the message unless gcd(a,m) = 1. This doesn't hold for b because b is not multipled into the equation, it is added, which is reversible under the modulus operation. – Jacob H Jul 30 '17 at 20:20

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 $>0$ because $m>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)>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<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>1$.

• a very clear explanation. worth reading all the references you cited. thanks. :) – Vishrant Jul 30 '17 at 21:27