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,

(ac)=ab+bc=(ab)+(bc)(a-c) = a-b+b-c = (a-b) + (b-c)

and so, from the congruence definitions we made above,

(ab)+(bc)=nk+nm=n(k+m)(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

159(mod2)15 \equiv 9\;(mod\;2)

and

95(mod2),9 \equiv 5\;(mod\;2),

then

155(mod2).15 \equiv 5\;(mod\;2).
2.

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

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

and

bc(modn)b \equiv c\;(mod\;n)

are true.

3.

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

ac(modn)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.
Already have an account?