Learn

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+c \equiv b\;(mod\;n)$

for a unknown. Subtract c from both sides to obtain:

$a \equiv b-c\;(mod\;n)$

From here, compute (b-c) % n, then solve for a as we did in the previous exercise. If we wanted to solve

$a-c \equiv b\;(mod\;n)$

for a unknown, then we would add c to both sides instead.

Now, suppose we wanted to solve

$ca \equiv b\;(mod\;n)$

for 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:

1. Our reduced problem becomes: 0 is congruent to 0 mod n. Since this is always true, any value of a can solve this congruence.
2. Our reduced problem becomes: 0 is congruent to r mod n, where r = b % n and 0 < r < n. Since this is never true, the congruence problem has no solutions.
3. Our reduced problem becomes: sa is congruent to r mod n, where s = c % n, r = b % n, 0 < s < n, and 0 <= r < n. There are infinitely many answers a for this problem; the smallest positive solution a can 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

$ca+d \equiv b\;(mod\;n)$

for a unknown. The procedure for solving for a here is a combination of the previous two.

### Instructions

1.

Find the smallest nonnegative value of a for which:

$a+6 \equiv 4\;(mod\;8)$

is true, and print whether or not the resulting congruence is true.

2.

Next, find the smallest nonnegative value of a for which:

$5a \equiv 4\;(mod\;2)$

is true, and print whether or not your resulting congruence is true.

3.

Lastly, find the smallest nonnegative value of a for which

$2a + 6 \equiv 4\;(mod\;8)$

is true, and print out whether or not your resulting congruence is true.