Using the Affine cipher, do we need $a^{-1}$ if we know gcd(a,26)=1?

Question

I have just attempted the affine cipher with the word "code"

$CODE = 02140304$

Lets choose our key as $(5,3)$, so our encryption is $y=5x+3$

$13211823=NVSX$

Now, to undo the code, I would have to do the euclidian algorithm to find $a^{-1} $ so I can say $x=a^{-1}(y-b)$, however why can't I just do $x=\frac{y-b}{a}$ to get $x$ without the use of the euclidian algorithm.

Answer 1

$5$ is relatively prime to $26$. This means that $5^{-1}$ exists modulo 26.

This allows us to solve all equations $5x = b$ (for all $b$), namely by multiplying both sides with $5^{-1}$: $x = 5^{-1} \cdot 5 x = 5^{-1} \cdot b$.

Division is just multiplication with the inverse. Writing division as you do, suggests working in the rationals, which is not what we're doing here. We multiply by the inverse instead (if it exists, but 5 was chosen wisely: we cannot use even numbers and 13 as these have no inverse).

To compute $5^{-1}$ use the extended Euclidean algorithm, and write $1 = \gcd(5,26)$ as $1 = 5c + 26d$, $c,d \in \mathbb{Z}$, so $5c \equiv 1 \bmod{26}$, and $c = 5^{-1}$.