$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?
 A: $$18x\equiv 1\pmod{25} \\ -7x\equiv1\pmod{25} \\ 7x\equiv-1\pmod{25}\\7x\equiv49\pmod{25} \\ \therefore x\equiv 7\pmod{25}$$
A: 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 $$
A: 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}$).
A: 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}$.
A: 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).
A: 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.
A: 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} }$$
