16
$\begingroup$

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.

  • 0
    I suppose we all have our own "ad hoc" methods. I would have "noticed" that multiplying by $3$ gives $x \equiv 21 \equiv 8$ (mod $13$). I have always believed that Gauss invented modular arithmetic. It is certainly discussed at length in Disquisitiones Arithmeticae, which I own a copy of.2012-07-24
  • 0
    It's not clear to me that the process always works, but it is interesting. It seems to me that the trick is that we get to replace our equation and hope for common prime factors between the coefficients.2012-07-24
  • 0
    @GeoffRobinson I am pretty sure Gauss did invent the notation, and I too have a copy of Disquisitiones Arithmeticae, but I cannot see anything in it along exactly the lines of my question, unfortunately.2012-07-24
  • 0
    It is not an algorithm in the precise sense of the word. The idea is basically to multiply or divide (on both sides) or add (or subtract) a multiple of the modulus (on either side) to get something which is equivalent, but "simpler". Repeating this vague process a number of times will give a solution (if the original has a solution) as at each step the multiple of $x$ on the left is going to get smaller, and the new congruence is equivalent to the previous one.2012-07-24
  • 0
    @Old John: Thanks. Yes Bill Dubuque's answer made what was going on reasonably clear.2012-07-24

3 Answers 3

18

Generally, if $\,b\,$ is coprime to the modulus $m$ then (by Bezout) it is invertible $\!\bmod m,\,$ so scaling $\,bx\equiv a\,$ by $\,b^{-1}\,$ we obtain the unique solution $\,x\equiv b^{-1}a.\,$ We can quickly compute $\,b^{-1}\pmod{\!m}\,$ by the extended Euclidean algorithm, but there are often more convenient ways for smaller numbers. We describe a few of these methods below, where we view $\, x\equiv b^{-1}a \equiv a/b\,$ as a modular fraction.

By Gauss' algorithm, scale $\rm\:\color{#C00}{\frac{A}B} \to \frac{AN}{BN}\: $ by the least $\rm\,N\,$ so that $\rm\, BN \ge 13,\, $ reduce mod $13,\,$ iterate.

$$\rm\displaystyle \ mod\ 13\!:\ \color{#C00}{\frac{7}9} \,\equiv\, \frac{14}{18}\, \equiv\, \color{#C00}{\frac{1}5}\,\equiv\, \frac{3}{15}\,\equiv\, \color{#C00}{\frac{3}2} \,\equiv\, \frac{21}{14} \,\equiv\, \color{#C00}{\frac{8}1}$$

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)

Or, simpler, allowing negative residues $\displaystyle\ \ \frac{7}9\,\equiv\, \frac{7}{\!-4\!\ \,}\,\equiv\,\frac{21}{\!\!-12\ \ \ \!\!}\,\equiv\, \frac{8}1$

This optimization of using balanced residues $0,\pm 1, \pm 2.\ldots$ works for modular arithmetic in general. 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$$

As you did, we can check if the 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.

More generally we can make the quotient exact by using 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 what is needed 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}$

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.).

The reformulation 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.

Beware $ $ Modular fraction arithmetic is valid only for fractions with denominator coprime to the modulus. See here for further discussion.

  • 0
    Thanks for the reference - so it was Gauss after all. The Gauss process is basically what I do, although I keep an eye out for any possible shortcuts, as in the example I gave.2012-07-24
  • 0
    @mathh As the linked post says, Gauss's algorithm requires *prime* modulus. Generally modular fractions [make sense only for denominators *coprime* to the modulus.](http://math.stackexchange.com/a/864588/242) Thus when scaling fractions we must restrict to scale factors *coprime* to the modulus, e.g. in your case we can do $\tag*{}$ ${\rm mod}\ 10\!:\ \dfrac{1}3\equiv \dfrac{3}9\equiv \dfrac{3}{-1} \equiv -3\equiv 7\ \ $2014-08-18
  • 0
    I'm sorry, I deleted the comment before you replied since I found it out. I would add to the above explanations that the denominators can be reduced if and only if the modulus is coprime to them.2014-08-18
  • 0
    @BillDubuque Is your notation $\mod p : a\equiv b$ as formal and accepted as $a\equiv b\pmod p$? I.e. do scientists, etc. use it?2014-08-18
  • 0
    @mathh It is less commonly used. I find it is clearer to students since it specifies the context first (vs. last) in normal reading order (left-to-right).2014-08-18
  • 0
    How do you prove that this algorithm always returns the answer for any prime modulus?2015-02-06
  • 0
    @user314 As stated, the $\rm\color{#c00}{denominators}$ are decreasing, so they eventually reach $\,\color{#c00}1\,$ (never $\,\color{#c00}0,\,$ else the denominator would be a proper factor of the prime modulus).2015-02-06
3

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.

1

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.