Linear congruence

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 , .