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

Difference between revisions of "Linear congruence"

(→‎Example 1: How to solve)
Line 1: Line 1:
 +
A '''Linear Congruence''' is a [[congruence]] mod p of the form
  
−
A '''Linear Congruence''' is a congruence mod p of the form
+
<math>ax+b\equiv c\pmod{p}</math>
  
−
<math>ax+b\equiv c\pmod{p}</math>
+
where <math>a, b, c</math>, and <math>p</math> are [[constant]]s and <math>x</math> is the [[variable]] to be solved for.
  
−
, where a, b, c, and p are constants, and x is the variable.
 
  
 
==Example I: How to solve==
 
==Example I: How to solve==
Line 10: Line 10:
 
Say <math>5x\equiv 7\pmod{8}</math>.  Find <math>x</math>.
 
Say <math>5x\equiv 7\pmod{8}</math>.  Find <math>x</math>.
  
−
Solution:
+
===Solution===
  
 
<math>5x\equiv 7\equiv 15\pmod{8}</math>, so  
 
<math>5x\equiv 7\equiv 15\pmod{8}</math>, so  
  
−
<math>x\equiv 3\pmod{8}</math>, because 5 is relatively prime to 8, we can divide by it.
+
<math>5\cdot5x\equiv 5\cdot7\pmod{8}</math> and thus
 +
 
 +
<math>x \equiv 3 \pmod 8</math>.
 +
 
 +
 
 +
Note that not every linear congruence has a solution.  For instance, the congruence equation
 +
<math>2x \equiv 3 \pmod 8</math> has no solutions.  A solution is guaranteed if and only if <math>a</math> is [[relatively prime]] to <math>p</math>.  If <math>a</math> and <math>p</math> are not relatively prime, say with [[greatest common divisor]] <math>d</math>, then we have two options:
 +
* if <math>d</math> [[divide]]s <math>b</math>, there will be a solution <math>\pmod \frac{p}{d}</math>
 +
* if <math>d</math> does not divide <math>b</math>, there will be no solution.

Revision as of 10:48, 15 August 2006

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

$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.
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Linear_congruence&oldid=9529"