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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – Jacob H
    Commented Jul 30, 2017 at 20:20

1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.