Learn

We only have one more property left to show! This final congruence property is called the transitive property, the statement of which goes like this:

Suppose we have the integers a, b, c, and n already defined with n > 0. If a is congruent to b mod n and b is congruent to c mod n, then it must be true that a is congruent to c mod n.

To prove the transitive property, we first suppose that a is congruent to b mod n and that b is congruent to c mod n. By definition of congruence, there exists an integer k such that (a-b) = n*k, and there exists another integer m such that (b-c) = n*m. Our task is to show that n divides (a-c), or that there exists some integer such that (a-c) is equal to n times that integer. But,

$(a-c) = a-b+b-c = (a-b) + (b-c)$

and so, from the congruence definitions we made above,

$(a-b) + (b-c) = nk + nm = n(k + m)$

We know that k + m is an integer because the sum of two integers is an integer. Therefore, we have shown that n divides (a-c), which proves that a is congruent to c mod n. We will use Python to prove the transitive property of congruences through multiple checkpoints.

### Instructions

1.

First, create the variables a, b, c, and n and set them to their correct values in the code editor, provided that we wanted to prove the following:

If

$15 \equiv 9\;(mod\;2)$

and

$9 \equiv 5\;(mod\;2),$

then

$15 \equiv 5\;(mod\;2).$
2.

Use our variable definitions of a, b, c, and n to print whether or not the following:

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

and

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

are true.

3.

Finally, use our variable definitions for a, b, c, and n to print whether or not:

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

# Take this course for free

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

## Or sign up using:

Already have an account?