Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Linear congruence

Revision as of 19:53, 25 April 2008 by I like pie (talk | contribs) (Wikification, formatting, links, category)

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.

Solving

Note that not every linear congruence has a solution. For instance, the congruence equation $2x\equiv3\pmod8$ has no solutions. A solution is guaranteed iff $a$ is relatively prime to $p$. If $a$ and $p$ are not relatively prime, let their greatest common divisor be $d$; then:

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

Example

Problem

Given $5x\equiv7\pmod8$, find $x$.

Solution 1

$7\equiv15\pmod8$, so $3x\equiv15\pmod8$. Thus, $x\equiv3\pmod 8$. Note that we can divide by $5$ because $5$ and $8$ are relatively prime.

Solution 2

Multiply both sides of the congruence by $5$ to get $25x\equiv35\pmod8$. Since $25\equiv1\pmod8$ and $35\equiv3\pmod8$, $x\equiv3\pmod8$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Linear_congruence&oldid=25397"