# congruences – How to find inverse of Coding and cryptography affine ciphers?

My lecturer for this module only uploads pdf’s and my knowledge of mathematics is very rusty as I decided to do this module as a standalone module. I am struggling to understand the deciphering aspect due to my weak knowledge of Euclid’s algorithm.

The enciphering of plaintext is of the formula:

``````c ≡ ap + b (mod 26), 0 ≤ c ≤ 25, (1)

where a and b are integers with gcd(a, 26) = 1. The key consists of the ordered pair (a, b).
``````

And the deciphering formula is:

``````p ≡ x(c − b) (mod 26), 0 ≤ p ≤ 25, (2)
where x is an inverse of a (mod 26).
``````

I have managed to calculate x, in which it consisted of backward substitution, but my problem arises where

``````p ≡ x(c − b) (mod 26) is written in the form of p ≡ cx+(SOME OTHER NUMBER) (mod 26)
``````

I do not understand how they simplified it to that form. I have been unable to find any videos on this and desperately need help.

This is an example from my notes:

``````As an example of an affine cipher, let a = 7 and b = 10 in (1) so that
c ≡ 7p + 10 (mod 26) and p ≡ 7(c − 10) (mod 26).
To find an inverse of 7 (mod 26), we solve the congruence 7x ≡ 1 (mod 26) by means
of the Euclidean Algorithm. Since 7x − 26y = 1 we have
26 = 3 × 7 + 5
7 = 1 × 5 + 2
5 = 2 × 2 + 1
Then substitute backwards:
1 = 5 − 2 × 2
= 5 − 2(7 − 1 × 5)
= 3 × 5 − 2 × 7
= 3 × (26 − 3 × 7) − 2 × 7
= 3 × 26 − 11 × 7
Thus 7(−11) − 26(−3) = 1 which shows that x ≡ −11 (mod 26).
Hence −11 ≡ 15 is an inverse of 7 (mod 26).
So for our affine cipher, we encipher with c ≡ 7p + 10 (mod 26), and the intended
recipient deciphers with p ≡ 15(c − 10) ≡ 15c + 6 (mod 26).
``````

This is the part I am confused about:

``````p ≡ 15(c − 10) ≡ 15c + 6 (mod 26)
``````

How did the brackets end up expanding to 6? I am certain there is a rule being used that is not general expansion and much related to the congruency, modulus and Euclid, and would like to know what it is so that I can solve this in future

Also, even links to good sources that will explain this whole aspect and as to why we take this approach for inverses etc. would be helpful