Solving linear congruences by hand: modular fractions and inverses When I am faced with a simple linear congruence such as 
$$9x \equiv 7 \pmod{13}$$
and I am working without any calculating aid handy, I tend to do something like the following:
"Notice" that adding $13$ on the right and subtracting $13x$ on the left gives:
$$-4x \equiv 20 \pmod{13}$$
so that $$x \equiv -5 \equiv 8 \pmod{13}.$$
Clearly this process works and is easy to justify (apart from not having an algorithm for "noticing"), but my question is this: I have a vague recollection of reading somewhere this sort of process was the preferred method of C. F. Gauss, but I cannot find any evidence for this now, so does anyone know anything about this, or could provide a reference? (Or have I just imagined it all?)
I would also be interested to hear if anyone else does anything similar.
 A: When the prime is a reasonably small one I'd rather find directly the inverse:
$$9^{-1}=\frac{1}{9}=3\pmod {13}\Longrightarrow 9x=7\Longrightarrow x=7\cdot 9^{-1}=7\cdot 3= 21=8\pmod {13}$$
But...I try Gauss's method when the prime is big and/or evaluating inverses is messy.
A: $bx\equiv a\pmod{\!m}$ has a unique solution $\!\iff\!b\,$ is coprime to the modulus $m$. If so, by Bezout $\,b\,$ is invertible $\!\bmod m,\,$  so scaling $\,bx\equiv a\,$ by $\,b^{-1}\,$ we obtain the unique solution $\,x\equiv b^{-1}a =: a/b.\,$  We can quickly compute $\,b^{-1}\pmod{\!m}\,$ by the extended Euclidean algorithm, but there are often more convenient ways for smaller numbers (e.g. here and here are a handful of methods applied).
We describe a few such methods below, viewing $\, x\equiv b^{-1}a \equiv a/b\,$ as a modular fraction.
[See here for the general method when the solution is not unique, i.e. when $\gcd(b,m)>1$].

The first, Gauss's algorithm, is based on Gauss's proof of Euclid's lemma via the descent $\,p\mid ab\,\Rightarrow\, p\mid a(p\bmod b).\,$ Generally it only works for prime moduli, but we can also execute  the general extended Euclidean algorithm in fraction form too (using multi-valued "fractions").
It works by repeatedly scaling $\rm\:\color{#C00}{\frac{A}B}\overset{\times\ N} \to \frac{AN}{BN}\: $ by the least $\rm\,N\,$ with $\rm\, BN \ge 13,\, $ then reducing mod $13$
$$\rm\displaystyle \ mod\ 13\!:\,\ \color{#C00}{\frac{7}9} \,\overset{\times\ 2}\equiv\, \frac{14}{18}\, \equiv\, \color{#C00}{\frac{1}5}\,\overset{\times \ 3}\equiv\, \frac{3}{15}\,\equiv\, \color{#C00}{\frac{3}2} \,\overset{\times\ 7}\equiv\, \frac{21}{14} \,\equiv\, \color{#C00}{\frac{8}1}\qquad\!\! $$
Denominators of the $\color{#c00}{\rm  reduced}$ fractions decrease $\,\color{#C00}{ 9 > 5 > 2> \ldots}\,$ so reach $\color{#C00}{1}\,$ (not $\,0\,$ else the denominator would be a proper factor of the prime modulus; it may fail for composite modulus)
Simpler: $ $ using $\rm\color{#0a0}{least}$ residues: $\displaystyle\  \ \frac{7}9\,\equiv\, \frac{7}{\!\color{#0a0}{-4}\!\ \,}\,\overset{\times\ 3}\equiv\,\frac{21}{\!\!-12\ \  \ \!\!}\,\equiv\, \color{#c00}{\frac{8}1}$
This optimization using $\rm\color{#0a0}{least\ magnitude}$ residues $\,0,\pm 1, \pm 2.\ldots$ often simplifies mod arithmetic. Here we can also optimize by (sometimes) cancelling obvious common factors, or by pulling out obvious factors of denominators, etc. For example
$$\frac{7}9\,\equiv\, \frac{\!-6\,}{\!-4\,}\,\equiv\frac{\!-3\,}{\!-2\,}\,\equiv\frac{10}{\!-2\,}\,\equiv\,-5$$
$$\frac{7}9\,\equiv\,\frac{\!-1\cdot 6}{\ \ 3\cdot 3}\,\equiv\,\frac{\!\,12\cdot 6\!}{\ \ \,3\cdot 3}\,\equiv\, 4\cdot 2$$

Or twiddle it as you did: $ $ check if  quotient $\rm a/b\equiv (a\pm\!13\,i)/(b\pm\!13\,j)\,$ is exact for small $\rm\,i,j,\,$ e.g.
$$ \frac{1}7\,\equiv \frac{\!-12}{-6}\,\equiv\, 2;\ \ \ \frac{5}7\,\equiv\,\frac{18}{\!-6\!\,}\,\equiv -3$$
When working with smaller numbers there is a higher probability of such optimizations being applicable (the law of small numbers), so it's well-worth looking for such in manual calculations.
Generally we can choose a congruent numerator giving an exact quotient by Inverse Reciprocity.
$\bmod 13\!:\ \dfrac{a}{b}\equiv \dfrac{a-13\left[\color{#0a0}{\dfrac{a}{13}}\bmod b\right]}b\,\ $ e.g. $\,\ \dfrac{8}9\equiv \dfrac{8-13\overbrace{\left[\dfrac{8}{\color{#c00}{13}}\bmod 9\right]}^{\large\color{#c00}{ 13\ \,\equiv\,\ 4\ }}}9\equiv\dfrac{8-13[2]}9\equiv-2$
Note that the value $\,\color{#0a0}{x\equiv a/13}\,$ is exactly what we need to make the numerator divisible by $b,\,$ i.e.
$\qquad\quad\bmod b\!:\,\ a-13\,[\color{#0a0}x]\equiv 0\iff 13x\equiv a\iff \color{#0a0}{x\equiv a/13}$
This is essentially an optimization of the Extended Euclidean Algorithm (when it takes two steps).
Note $ $ Gauss' algorithm is my name for a special case of the Euclidean algorithm that's implicit in Gauss' Disquisitiones Arithmeticae, Art. 13, 1801. I don't know if Gauss  explicitly used this algorithm elsewhere (apparently he chose to avoid use or mention of the Euclidean algorithm in Disq. Arith.). Gauss does briefly mention modular fractions in Art. 31 in Disq. Arith.
The reformulation above in terms of fractions does not occur in Gauss' work as far as I know.  I devised it in my youth before I had perused Disq. Arith. It is likely  very old but I don't recall seeing it in any literature. I'd be very grateful for any historical references.
See here for further discussion, including a detailed comparison with the descent employed by Gauss, and a formal proof of correctness of the algorithm.
Beware $ $ Modular fraction arithmetic is valid only for fractions with denominator coprime to the modulus. See here for further discussion.
A: 9x = 7 mod 13  
9x = 7 + 13n
9x = 20 for n = 1
9x = 33 for n = 2
9x = 46 for n = 3  
9x = 59 for n = 4  
9x = 72 for n = 5
Then x = 8 mod 13
You arrive at the correct answer before n = 13.
A: Another offbeat process but with algorithmic potential.
Solve $9x \equiv 7 \pmod{13}$.
$\quad 9x = 7 + 13y \implies 0 \equiv 1 + y \pmod{3} \implies y \equiv 2 \pmod{3}$
and
$\quad y : 2 \;  \mid \; 7 + 13y = 33 \quad \quad \text{NO GOOD!}$
$\quad y : 5 \;  \mid \; 7 + 13y = 72 \quad \quad \text{AND is divisible by } 9$
So,
$\tag{ANS} x \equiv 8 \pmod{13}$
A: When presented with
$\tag 1 ax \equiv b \pmod{n}$
if $a \mid b$ the solution is right in front of you.
But there is also a 'plug in' solution if $a \mid n-1$ or  $a \mid n+1$:
If $a \mid n-1$ then $x = \Large(\frac{n-1}{a}) \normalsize (-b)$ solves $\text{(1)}$.
If $a \mid n+1$ then $x = \Large(\frac{n+1}{a}) \normalsize (b)$ solves $\text{(1)}$.
Can we 'make hay' with the OP's linear congruence?
$\quad 9x \equiv 7 \pmod{13} \; \text{ iff } \; -4x \equiv 7 \pmod{13} \; \text{ iff }$
$ \quad  4x \equiv -7 \pmod{13} \; \text{ iff } \; 4x \equiv 6 \pmod{13}$
We are in business now with $4x \equiv 6 \pmod{13}$ since $4 \mid 12$; a solution is
$\quad x = \Large(\frac{n-1}{a}) \normalsize (-b) = (3)(-6) = -18 \equiv 8 \pmod{13}$

Here is an example where the $n + 1$ manipulation can be used:
$\quad 5x \equiv 1 \pmod{17} \; \text{ iff } \; -12x \equiv 1 \pmod{17} \; \text{ iff }$
$ \quad  12x \equiv -1 \pmod{17} \; \text{ iff } \; 12x \equiv 16 \pmod{17} \; \text{ iff } \; 6x \equiv 8 \pmod{17}$
We are in business now with $6x \equiv 8 \pmod{17}$ since $6 \mid 18$; a solution is
$\quad x = \Large(\frac{n+1}{a}) \normalsize (b) = (3)(8) = 24 \equiv 7 \pmod{17}$
