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 b and c 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

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?