17
$\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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Geoff Robinson Jul 24 '12 at 15:08
  • $\begingroup$ 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. $\endgroup$ – Andrew Jul 24 '12 at 15:09
  • $\begingroup$ @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. $\endgroup$ – Old John Jul 24 '12 at 15:13
  • $\begingroup$ 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. $\endgroup$ – Old John Jul 24 '12 at 15:16
  • $\begingroup$ @Old John: Thanks. Yes Bill Dubuque's answer made what was going on reasonably clear. $\endgroup$ – Geoff Robinson Jul 24 '12 at 18:46
20
$\begingroup$

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.


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)

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

This optimization using least magnitude residues $0,\pm 1, \pm 2.\ldots$ often simplifies modular 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 as you did: $ $ 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}$

This can be viewed as an optimization of the Extended Euclidean Algorithm in the case when it terminates in 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.).

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.

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Old John Jul 24 '12 at 15:21
  • $\begingroup$ @mathh As the linked post says, Gauss's algorithm requires prime modulus. Generally modular fractions make sense only for denominators coprime to the modulus. 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\ \ $ $\endgroup$ – Bill Dubuque Aug 18 '14 at 16:44
  • $\begingroup$ 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. $\endgroup$ – user26486 Aug 18 '14 at 16:51
  • 1
    $\begingroup$ @Michael Yes, it shows $\bmod 13\!:\ 9^{-1}\equiv \color{#0a0}2\times\color{#0a0}3\times\color{#0a0}7\equiv 3.\ $ The sequence of *decreasing* multiples of $9$ is comprised by the reduced denominators (in red in the answer), i.e. as below $\endgroup$ – Bill Dubuque Jan 15 at 15:51
  • 2
    $\begingroup$ $${\begin{align}&9\ \overset{\large \times\color{#0a0} 2}\longrightarrow\ 5\overset{\large \times\color{#0a0} 3}\longrightarrow 2\,\overset{\large \times\color{#0a0} 7}\longrightarrow\, 1\\[.4em] \Rightarrow\ \ & 9\ \ \times\ \ \color{#0a0}2\ \times\ \color{#0a0}3\ \times\ \color{#0a0}7\equiv 1\\[.4em] \Rightarrow\ \ &9^{-1}\!\equiv \color{#0a0}2\ \times\ \color{#0a0}3\ \times\ \color{#0a0}7\equiv 3& \end{align}\quad\qquad}$$ $\endgroup$ – Bill Dubuque Jan 15 at 15:51
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.