$18x\equiv1\pmod{ 25}$. Computing inverses modulo a square.

I just got started with discrete math and modular arithmetic and I'm trying to get good at modular congruences. I was trying to solve this exercise:

$$18x\equiv1\bmod {25}$$

Here's what I've tried:

$$18x\equiv1\text{ }(25) \iff 18x \equiv 26\text{ } (25) \mathop{\iff}^{\text{div by 2}} 9x \equiv 13\text{ }(25)\iff 9x \equiv -1\text{ }(25)$$

Then I'm not quite sure how to proceed. This is the first exercise of this kind I'm attempting, and for a bit I thought I was onto something.

What am I missing?

Solution 1:

$$18x\equiv 1\pmod{25} \\ -7x\equiv1\pmod{25} \\ 7x\equiv-1\pmod{25}\\7x\equiv49\pmod{25} \\ \therefore x\equiv 7\pmod{25}$$

Solution 2:

First, you should have mentioned your reduction is valid because $2$ is coprime to $25$, hence a unit mod. $25$. There remains to find the inverse of $9\bmod 25$. This inverse is deduced from a Bézout's relation between $9$ and $25$.

However, it is as simple to determine directly the inverse of $18$. Even if there is no obvious Bézout's relation, you have at your disposal the Extended Euclidean algorithm. Here is how it goes:

\begin{array}{rrrr} r_i&u_i&v_i&q_i \\ \hline 25&0&1 \\ 18&1&0&1\\ \hline 7&-1&1&2 \\ 4&3&-2 & 1 \\ 3&-4&3&1 \\ 1&7&-5 \\ \hline \end{array} Therefore, a Bézout's relation is $\;7\cdot 18-5\cdot 25=1$, the inverse of $18\bmod 25=7$, i.e. the solution is $$18 x\equiv 1\iff x\equiv 7\cdot 1=7\mod 25.$$

Some explanations:

The extended Euclidean theorem asserts that all remainders in the classical Euclidean algorithm are linear combinations of the two given numbers.

Indeed, at the $i$-th step, denote $r_i, q_i$ the remainder and the quotient, and $u_i, v_i$ the coefficients of the linear combination for $r_i$. A close examination of the classical Euclidean algorithm yields a recursive relation for the coefficients $u_i,v_i$ (here, $25$ and $18$ are considered as $r_{-1}$ and $r_0$ respectiively).: $$u_{i+1}=u_{i-1}-q_iu_i,\qquad v_{i+1}=v_{i-1}-q_iv_i $$