Here is a problem people face at work: suppose a team of four must complete a three-task project. Everyone decides to assign the tasks so that everyone works on the same number of tasks. However, they cannot assign these tasks evenly. The next day, one team member gets assigned to a different team. The remaining team of three attempts to divide the project tasks again and succeeds! This leads us to wonder: how will we know if we can assign the same number of tasks to each team member? We will answer the question through definitions.

First, we say that a divides b if we can find an integer k such that b = a * k. If a does not divide b, then b/a leaves a remainder. The operation for finding this remainder is called modular arithmetic, and the operator used to perform modular arithmetic is called the modulus. We express modulus with %, and the script:

print(a % b)

outputs the remainder of a/b.

Finally, we say that a is congruent to b mod n (where mod is short-hand for modulus) if n divides (a-b); in other words, a is congruent to b mod n if there is an integer k such that a-b = k*n. In mathematical symbols, we write a is congruent to b mod n as:

ab(modn)a \equiv b\;(mod\;n)

Python can check congruences by verifying that (a-b) % n = 0. The script:

# Define a, b, and n such that n > 0 print((a - b) % n == 0)

will return True if (a - b) % n = 0 and False otherwise.

Note two things: first, n is defined to be positive and, second, the remainder r is a positive integer such that 0 <= r < n. Also, n cannot be 0 because if n = 0 then, by definition of congruence, 0 divides a-b, which is never true because 0 does not divide any number.

The next exercise will motivate congruences by explaining their relevance to cryptography. After that, we will define three congruence properties, then we will solve simple kinds of congruence problems. For now, however, we will ask you to use Python to check if two integers are congruent to each other mod n.



First, print whether or not:

71(mod6)7 \equiv 1\;(mod\;6)

Now print whether or not the following is true:

25(mod3)2 \equiv 5\;(mod\;3)

Finally, print out whether or not:

65(mod4)6 \equiv 5\;(mod\;4)

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?