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

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

abc(modn)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

acb(modn)a-c \equiv b\;(mod\;n)

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

Now, suppose we wanted to solve

cab(modn)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+db(modn)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+64(mod8)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:

5a4(mod2)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+64(mod8)2a + 6 \equiv 4\;(mod\;8)

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

Take this course for free

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?