Home >> Science & Nature >> Science

How to Solve Linear Congruence

A linear congruence is a modular mathematical function relating a variable (x) to three different integers through the formula ax ≡ b (mod m). Here, a and b are integers and m is a non-zero integer. Solving a linear congruence requires an understanding of some tricky mathematical concepts. Through a few simple steps, these problems can be mastered.

Instructions

- 1
  Calculate the greatest common divisor (g) between integer a and m. If the integer b cannot be divided by this greatest common divisor, then x in this linear congruence has no solution. For example, in the case 6x ≡ 2 (mod 3), then the greatest common divisor is 3. However, 2 is not divisible by 3 without a remainder, therefore no solutions exist for this linear congruence problem.
- 2
  Calculate the number of solutions and the range of possible solution values. The greatest common divisor dictates the number of integer solutions for x from the series (0, 1, 2, ... m-1). For example, in the case 3x ≡ 6 (mod 9), the greatest common divisor is 3. Therefore three solutions exist for this linear congruence problem. Possible solutions are (0, 1, 2, 3, 4, 5, 6, 7, 8).
- 3
  Solve g = r*a + s*m using the extended Euclidean algorithm, where r and s are additional integers. In the example, 3 = r*3 + s*9 can yield r = -2, s = 1.
- 4
  Find one solution by equating x to (r*b/g). This and all solutions are congruent with g (mod (m/g)). Continuing the example, x = (-2*6/3) = -4, which is congruent with 2 (mod 3).
- 5
  Calculate the solutions for x. In the example, the solutions for x are (2, 5, 8).

Science