Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

3 Answers 3

up vote 15 down vote accepted

By Gauss' algorithm, scale $\rm\:\color{#C00}{\frac{A}B} \to \frac{AN}{BN}\: $ by the least $\rm\,N\,$ so that $\rm\, BN > 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.}$

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.

Note $ $ Gauss' algorithm is my name for a special case of the Euclidean algorithm that's implicit in Gauss' Disq. Arith. I don't recall if Gauss explicitly used this algorithm. Follow said link for more.

share|improve this answer
    
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. –  Old John Jul 24 '12 at 15:21
    
@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\ \ $ –  Bill Dubuque Aug 18 at 16:44
    
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. –  mathh Aug 18 at 16:51
    
@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? –  mathh Aug 18 at 16:54
    
@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). –  Bill Dubuque Aug 18 at 17:05

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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