Solving Linear Congruence

Solving Linear Congruence

• The video will show the basic technique of solving linear congruence and how to use a Texas Instruments graphing calculator to help generate congruence classes of modulo M.
• Requires a solid understanding of the greatest common divisor (GCD).
• GCD can be found by identifying the greatest common factor of the factors of both numbers.
• If one of the two numbers is prime, the GCD is 1.

Linear Congruence Form

• A linear congruence has the form ax ≡ b mod m, where a, b, and m are integers.
• Example: 29 ≡ 5 mod 8 is a least residue system mod 8.
• A least residue system mod 8 is a set of integers that are a multiple of 8.

Three Outcomes of Solving Linear Congruence

• Unsolvable case
• Single solution case
• More than one solution case

Unsolvable Case

• Two steps to identify unsolvable cases:
  • Find the GCD of a and m.
  • Test if the GCD evenly divides b.
• If the GCD doesn't divide b, the linear congruence is unsolvable.
• Example: 2x ≡ 51 mod 8 is unsolvable because GCD(2, 8) = 2, and 2 does not divide 51.

Single Solution Case

• The GCD test is a necessary step when solving any linear congruence.
• Example: 4x ≡ 26 mod 7
  • Find the greatest common divisor of 4 and 7, which is 1.
  • Check if 26 can be divided by 1 (it can).
• Since the GCD is 1 and it divides 26, the linear congruence will have a single solution.
• Isolate x to solve the linear congruence - But it is not an equation.
• If both a and b can be divided by an integer c, rewrite the linear congruence.
• Consider the residues and add or subtract multiples of m to b to make it divisible by a.
• Example:
  • 4x ≡ 26 mod 7 can be rewritten as 2x ≡ 13 mod 7 (dividing by 2).
  • 2x ≡ 6 mod 7 (subtracting 7 from 13).
  • x ≡ 3 mod 7 (dividing by 2).

More Challenging Example for Single Solution

• 25x ≡ 15 mod 29
  • GCD(25, 29) = 1 and 15 can be divided by 1.
  • Divide 25 and 15 by 5 resulting in 5x ≡ 3 mod 29.
  • Explore multiples of 29 to find a value that allows division by 5 (e.g., -55).
  • 5x ≡ -55 mod 29
  • x ≡ -11 mod 29
  • Add 29 to -11 for a positive value: x ≡ 18 mod 29.

More Than One Solution

• There will be multiple solutions.
• Check things out with the GCD test.
• Find the greatest common denominator of a and m and check if b is divisible by it.
• Example: 9x ≡ 42 mod 6
  • GCD(9, 6) = 3, and 42 is divisible by 3 so there will be 3 solutions

Solving Multiple Solution Congruence

• If every integer can be divided by the GCD, divide all by the GCD to simplify.
• Example: 9x ≡ 42 mod 6 becomes 3x ≡ 14 mod 2.
• Walk down that b by multiples of m to get something that can be divided by a.
• The simplified form is called the solution in the least residue system.
• Find multiple (three) values for x using a parametric method.
• Number from 0 to number of solutions -1 (so to 2 in the example) to create a table of values.
• Generate values for b using the equation b = mt + solution, with t taking on the values in the table.
• Express the final solutions with the original modulo: x ≡ solution mod m.
• From the example of 9x ≡ 42 mod 6, after simplification we get x ≡ 0 mod 2
  • so the equation becomes b = 2t + 0
  • we start with table 0, 1, 2
  • the b table becomes 0, 2, 4
  • the final solution is then x ≡ 0 mod 6, 2 mod 6, 4 mod 6

Additional Example of Multiple Solutions

• 6x ≡ 15 mod 21
  • GCD(6, 21) = 3, and 15 is divisible by 3.
  • Divided by 3 on both sides: 2x ≡ 5 mod 7
  • Use multiples of 7 from 5 to find something that can be divided by 2. It is possible to go up or down.
  • Choosing to go up: 2x ≡ 12 mod 7 which gives x ≡ 6 mod 7
  • Use parametric form and table again to find the other two solutions
  • We count 0, 1, 2 for the table again
  • the equation in this case is b = 7t + 6, with t taking on the values 0, 1, 2 --> so b = 6, 13, 20
  • So final solution is x ≡ 6 mod 21, x ≡ 13 mod 21, and x ≡ 20 mod 21

Graphing Calculator Help

• Texas Instruments ti-84 and ti-nspire series have a function called "seq" (sequence) to generate a list of values.
• Syntax: seq(expression, variable, low, high, step).
• Example: seq(3x + 1, x, -2, 4, 1) generates a list from the expression 3x + 1 with x from -2 to 4, stepping by 1.
• Can be used to generate least residue systems in mod M.
• Example: x ≡ 5 mod 8 can be coded as seq(8x + 5, x, -4, 4, 1).
• Example: x ≡ 0 mod 7 can be coded as seq(7x, x, 0, 6, 1).