Now, we will focus on solving linear congruences, or congruences with the unknown variable contained within a linear expression. Linear expressions are expressions in the form
ax + b, where a and b are constants and
x is our unknown variable. Solving for the unknown variable in a congruence problem is almost identical to solving for
x in a linear equation: the catch is that each computation in the linear congruence is mod n. In other words, for every operation we perform, we must perform modular arithmetic (% n) on each term except n itself. We will focus on three types of linear congruences. (Note: for all cases, suppose c and d are known positive integers between 1 and n.)
First, suppose we wanted to solve
a unknown. Subtract c from both sides to obtain:
From here, compute
(b-c) % n, then solve for a as we did in the previous exercise. If we wanted to solve
a unknown, then we would add c to both sides instead.
Now, suppose we wanted to solve
a unknown. Then we can perform modular arithmetic on both c and b mod n (i.e.
c % n and
b % n) to reduce the problem to one of three outcomes:
- Our reduced problem becomes: 0 is congruent to 0 mod n. Since this is always true, any value of a can solve this congruence.
- Our reduced problem becomes: 0 is congruent to
rmod n, where
r = b % nand
0 < r < n. Since this is never true, the congruence problem has no solutions.
- Our reduced problem becomes:
sais congruent to
rmod n, where
s = c % n,
r = b % n,
0 < s < n, and
0 <= r < n. There are infinitely many answers
afor this problem; the smallest positive solution
acan be discovered by:
# Define s, r, and n for a in range(0, n): if((s * a - r) % n == 0): print(a) break
Lastly, suppose we wanted to solve
a unknown. The procedure for solving for
a here is a combination of the previous two.
Find the smallest nonnegative value of
a for which:
is true, and print whether or not the resulting congruence is true.
Next, find the smallest nonnegative value of a for which:
is true, and print whether or not your resulting congruence is true.
Lastly, find the smallest nonnegative value of a for which
is true, and print out whether or not your resulting congruence is true.