# Difference between revisions of "Linear congruence"

m (→Solution 1) |
m (→Solution 1) |
||

Line 13: | Line 13: | ||

===Solution 1=== | ===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. | + | <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. <math>/square</math> |

===Solution 2=== | ===Solution 2=== |

## Revision as of 00:08, 19 December 2009

A **Linear Congruence** is a congruence mod p of the form
where , , , and are constants and is the variable to be solved for.

## Solving

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

- if divides , there will be a solution
- if does not divide , there will be no solution

## Example

### Problem

Given , find .

### Solution 1

, so . Thus, . Note that we can divide by because and are relatively prime.

### Solution 2

Multiply both sides of the congruence by to get . Since and , .