Linear congruence

Revision as of 10:50, 15 August 2006 by JBL (talk | contribs) (Solution)

A Linear Congruence is a congruence mod p of the form

$ax+b\equiv c\pmod{p}$

where $a, b, c$, and $p$ are constants and $x$ is the variable to be solved for.


Example I: How to solve

Say $5x\equiv 7\pmod{8}$. Find $x$.

Solution

$5x\equiv 7\equiv 15\pmod{8}$, so

$x \equiv 3 \pmod 8$. Note that we can divide by 5 because 5 and 8 are relatively prime.

An alternative method is to note that $5\cdot 5 \equiv 25 \equiv 1 \pmod{8}$, so

$5\cdot5x\equiv 5\cdot7\pmod{8}$ and thus

$x \equiv 3 \pmod 8$.


Note that not every linear congruence has a solution. For instance, the congruence equation $2x \equiv 3 \pmod 8$ has no solutions. A solution is guaranteed if and only if $a$ is relatively prime to $p$. If $a$ and $p$ are not relatively prime, say with greatest common divisor $d$, then we have two options:

  • if $d$ divides $b$, there will be a solution $\pmod \frac{p}{d}$
  • if $d$ does not divide $b$, there will be no solution.