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:

- 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
`r`

mod n, where`r = b % n`

and`0 < r < n`

. Since this is never true, the congruence problem has no solutions. - 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.