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

5 Answers 5

Reset to default
29
$\begingroup$

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

$\endgroup$
32
  • $\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, 2012 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, 2014 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, 2014 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, 2019 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, 2019 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$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ For more examples of this technique see this. $\endgroup$
    – CopyPasteIt
    Sep 14, 2020 at 3:08
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .