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

Question

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?

Answer 1

Perform the Euclidean algorithm to find $\gcd(18,25)$:

$$25=18\times 1+7$$ $$18=7\times 2+4$$ $$7=4\times 1+3$$ $$4=3\times 1+1$$

which, backwards, gives you:

$$\begin{array}{rl}1&=4\times1+3\times(-1)\\&=4\times 1+(7\times 1+4\times (-1))\times (-1)\\&=7\times(-1)+4\times 2\\&=7\times(-1)+(18\times 1+7\times(-2))\times 2\\&=18\times 2+7\times (-5)\\&=18\times 2+(25\times 1+18\times(-1))\times(-5)\\&=25\times(-5)+18\times 7\end{array}$$

The point of this calculation was to express $1=\gcd(25, 18)$ in the form $25a+18b$ with $a, b$-integers.

Once you have that, you will see that the factor multiplying $18$ (in this case, $7$) acts as an inverse of $18\pmod{25}$. In particular, $7\times 18\equiv 1\pmod{25}$, and also, if $18x\equiv 1\pmod{25}$, by multiplying by $7$ you get $7\times 18x\equiv 7\pmod{25}$, i.e. $x\equiv 7\pmod{25}$.

Answer 2

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

Answer 3

Hint:

$9x\equiv13\pmod{25}$ means $9x\equiv13+2\times25=63\pmod{25}$

(and, as pointed out in comments, $9x\equiv13\pmod{25}$ does not mean $9x\equiv-1\pmod{25}$).

Answer 4

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

Answer 5

You're missing Bézout's identity. This identity is crucial for handling multiplicative inverses in $\mathbb{Z} / n \mathbb{Z}$. E.g.,

invertible elements
$a \in \mathbb{Z} / n \mathbb{Z}$ has inverse $x$ iff there is some integer $k $ such that $ax = kn + 1$ iff (by Bézout's identity) $a$ and $n$ are relatively prime. This means that one should be careful when dividing in $\mathbb{Z} / n \mathbb{Z}$ : you can divide by $b$ iff $b$ is relatively prime to $n$.

In a concrete situation like yours, you can find the inverse of $a$ using the extended Euclidean algorithm.

Answer 6

You can procede (from your false conclusion) like this: $$9x\equiv 24 \pmod {25}\implies 3x\equiv 8 \pmod {25} $$

$$\implies 3x\equiv 33 \pmod {25} \implies \boxed{x\equiv 11 \pmod {25} }$$

---

Now the correct result is: $$9x\equiv 13 \pmod {25}\implies 9x\equiv -12 \pmod {25} $$

$$\implies 3x\equiv -4 \pmod {25} \implies 3x\equiv 21 \pmod {25} \implies\boxed{x\equiv 7 \pmod {25} }$$

Answer 7

Easy way: $ $ lift inverse $\!\bmod 5\!:\ \overbrace{\color{#0a0}{a'} \equiv {\large \frac{1}{18}\equiv \frac{6}3}\equiv \color{#0a0}2}^{\!\!\!\textstyle\Rightarrow\, 18\cdot \color{#0a0}2 = \color{#0a0}{1\! +\! 7\cdot 5}}\,$ up to $\!\bmod 5^2$ as follows $\!\!\bmod \color{#c00}{5^{\large 2}}\!: \dfrac{1}{18}\!\equiv\!\dfrac{\color{#0a0}2}{18\!\cdot\!\color{#0a0}2} \!\equiv\! \dfrac{\color{#0a0}2}{\color{#0a0}{1\!+\!7\cdot 5}}\equiv\,\overbrace{2(1\!-\!7\cdot 5)}^{\large \equiv \ 7},\, $ by $\ \color{#c00}{5^{\large 2}\!\equiv 0}.\,$ Generally if $\,{\overbrace{1/a\equiv a'\pmod{\!n}}^{\!\!\textstyle\Rightarrow\ a\color{#0a0}{a' = 1+j\,n}}}\,$

$\!\!\bmod \color{#c00}{n^2}\!:\ \dfrac{1}{a}\,\equiv\,\dfrac{\color{#0a0}{a'}}{a\color{#0a0}{a'}}\!\equiv \dfrac{\color{#0a0}{a'}}{\color{#0a0}{1+j\,n}}\equiv\, a'(1-j\,n),\ $ by $\ \color{#c00}{n^2\equiv 0},\,$ lifts inverse $\!\bmod n\,$ up to $\!\bmod{n^2}$

because, $ $ we have that: $\ (\color{#0a0}{1+j\,n})\,(1-j\,n)\:\! =\:\! 1-j^2\color{#c00}{n^2}\equiv 1,\, $ so $\ (\color{#0a0}{1+j\,n})^{-1}\equiv 1-j\,n$.

This can be viewed as using Hensel lifting (Newton's method) to compute inverses. In general, as above, it is trivial to invert a unit + nilpotent by using a (terminating) geometric series, which is a special case of the general method of simpler multiples.

Of course we can also use general inversion methods $\!\bmod n^2,\,$ but usually they will be less efficient. There are a few worked examples using a handful of such methods (including all those in the other answers) presented here and here and here. This includes most all the common known methods (and their optimizations).