Difference between revisions of "Linear congruence"

(Solution)
m
 
(5 intermediate revisions by 4 users not shown)
Line 1: Line 1:
A '''Linear Congruence''' is a [[congruence]] mod p of the form  
+
A '''Linear Congruence''' is a [[congruence]] [[modular arithmetic|mod]] p of the form  
 +
<cmath>ax+b\equiv c\pmod{p}</cmath>
 +
where <math>a</math>, <math>b</math>, <math>c</math>, and <math>p</math> are [[constant]]s and <math>x</math> is the [[variable]] to be solved for.
  
<math>ax+b\equiv c\pmod{p}</math>
+
==Solving==
 +
Note that not every linear congruence has a solution. For instance, the congruence equation <math>2x\equiv3\pmod8</math> has no solutions. A solution is guaranteed [[iff]] <math>a</math> is [[relatively prime]] to <math>p</math>. If <math>a</math> and <math>p</math> are not relatively prime, let their [[greatest common divisor]] be <math>d</math>; then:
 +
* 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
  
where <math>a, b, c</math>, and <math>p</math> are [[constant]]s and <math>x</math> is the [[variable]] to be solved for.
+
==Example==
 +
===Problem===
 +
Given <math>5x\equiv7\pmod8</math>, find <math>x</math>.
  
 +
===Solution 1===
 +
<math>7\equiv15\pmod8</math>, so <math>5x\equiv15\pmod8</math>. Thus, <math>x\equiv3\pmod 8</math>. Note that we can divide by <math>5</math> because <math>5</math> and <math>8</math> are relatively prime.
  
==Example I: How to solve==
+
===Solution 2===
 +
Multiply both sides of the congruence by <math>5</math> to get <math>25x\equiv35\pmod8</math>. Since <math>25\equiv1\pmod8</math> and <math>35\equiv3\pmod8</math>, <math>x\equiv3\pmod8</math>.
  
Say <math>5x\equiv 7\pmod{8}</math>.  Find <math>x</math>.
+
[[Category:Number theory]]
 
 
===Solution===
 
 
 
<math>5x\equiv 7\equiv 15\pmod{8}</math>, so
 
 
 
<math>x \equiv 3 \pmod 8</math>.  Note that we can divide by 5 because 5 and 8 are [[relatively prime]].
 
 
 
An alternative method is to note that
 
<math>5\cdot 5 \equiv 25 \equiv 1 \pmod{8}</math>, so
 
 
 
<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.
 

Latest revision as of 14:52, 3 August 2022

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 $5x\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$.