Section6.1Solving Linear Congruences

The main goal in this section is to completely solve all linear congruences \(ax\equiv b\) mod (\(n\)). In order to do that, we will use several facts, of which the most important is this.

Before going on, you can tell me right now which of these has a solution and which one doesn't.

  • \(7x\equiv 8\) mod (15)
  • \(6x\equiv 8\) mod (15)
  • \(7x\equiv 8\) mod (14)
  • \(6x\equiv 8\) mod (14)

Subsection6.1.1The nitty-gritty of solving

Just like in linear algebra or calculus, though, it's not enough to know when you have solutions; you want to actually be able to construct solutions - all of them, if possible.

  • Consider the proof above; we don't care about \(y\) (other than that it exists, and it does).
  • So, if we have one solution \(x_0,y_0\), then all solutions are \[x_0+\frac{n}{d}t\qquad t\in\mathbb{Z}\text{ where }d=gcd(a,n)\; .\]
  • The proof also gives us the exact number of solutions, because letting \(t\) go from 0 to \(d-1\) will give all different solutions.
So we've reduced the entire problem of solving one linear congruence to finding one solution to a linear Diophantine equation, which we know how to do.

Example6.1.2

Let's solve \[12x\equiv 9\text{ mod }(15)\; .\]

  • Here, \(gcd(a,n)=3\) so we will have 3 solutions, all separated by \(\frac{n}{d}=\frac{15}{3}=5\).
  • Trying by guess and check small values gives us
    • \(12(1)=12\not\equiv 9\),
    • but \(12(2)=24\equiv 9\) mod (15)!
  • So \(x=2\) is our \(x_0\).
  • Then we add \(5\) to each of these, and we see that \(x=[2],[7],[-3]\) all work.
  • Alternately, \[2+5t,\, t\in\mathbb{Z}\] is the general solution.