Basic property of modular arithmetic equations

44 Views Asked by At

I am attempting a basic affine cypher decryption and am left with the following systems of equations:

$$25a +b = 13 \mod 26 \text{ }(1)$$

$$14a +b = 6 \mod 26 \text{ }(2)$$

Is it correct to subtract $(2)$ from $(1)$ to get:

$$11a = 7 \mod 26$$

and solve the resulting equation for $a$? And then sub this value back into $(1)$ or $(2)$ and solve for $b$? Thanks!

1

There are 1 best solutions below

2
On BEST ANSWER

Yes, what you suggested is fine.

Use Euclidean algorithm to find $11^{-1}\pmod{26}$.

$$26=2(11)+4$$

$$11=2(4)+3$$

$$4=3+1$$

Hence \begin{align}1&=4-(11-2(4)) \\ &=3(4)-11\\ &=3(26-2(11))-11 \\ &=3(26)-7(11)\end{align}

That is $$11^{-1}\equiv-7 \pmod{26}$$

$$a \equiv (-7)(7) \equiv -49 \equiv 52-49 \equiv 3 \pmod{26}$$

$$b \equiv 6-14(3) \equiv -36 \equiv -10 \equiv 16 \pmod{26}$$