Divisibility and Congruence

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

(No.)

Divisibility and Congruence

From “Beginning Activity 1 (Definition of Divides, Divisor, Multiple),” “Beginning Activity 2 (Calendars and Clocks),” and “Congruence” in section 3.1 and this divisibility discussion.

The Ideas

There are good solutions to these in the discussion, but let’s check a few: determine whether the following claims are true or false, and explain your decisions in terms of the definitions of divisibility or congruence.

1. 4 | 20. This can be read as “4 divides 20,” and so is true
2. 4 | -8. This is also true, -8 = 4 × -2. a|b only requires that b is an integer multiple of a, it doesn’t have to be a positive integer.
3. 4 | 13 This is false, since no integer times 4 equals 13.
4. 4 ≡ 13 (mod 3). This can be read as “4 is congruent (modulo 3) to 13,” and there are two ways to interpret it:
   • The textbook’s definition, i.e., 3 | (13 - 4).
   • Or 4 and 13 have the same remainder when divided by 3 (this interpretation was shared in the discussion, but not in the textbook — at least not yet).
   • These are equivalent because if 4 = 3c + r, and 13 = 3k + r then 13 - 4 = 3c + r - (3k + r) = 3(c-k) which is divisible by 3; similarly if 13 - 4 is a multiple of 3, and you write 4 = 3c + r and 13 = 3k + s, then for 13 - 4 to be a multiple of 3, the remainders r and s must be equal.
   • Using, say, the textbook’s definition, we see that 4 ≡ 13 (mod 3) is true because 13 - 4 = 9 which is divisible by 3.
5. 4 ≡ 13 (mod 6). This is false, since 4/6 has remainder 4, but 13/6 has remainder 1.
6. 4 ≡ 20 (mod 3) This is also false, since 20 - 4 = 16, which is not divisible by 3.
7. -8 ≡ -23 (mod 5). This is true because (-23) - (-8) = -15 which is divisible 5. Modular congruence applies to negative numbers as well as to positive ones.

An Application

Product bar codes, like this one:

We tried an experiment in which students read barcodes to me but skipped one digit; based on this experiment, it seems that professors have the magical superpower of being able to correctly guess a missing digit in a barcode (it’s less clear why they need that superpower, of course).

It’s not a magical superpower, of course, it’s actually a feature built in to barcodes. In particular, every barcode number is chosen so that if you add up the digits in odd-numbered positions (the 1st, 3rd, 5th, 7th, 9th, and 11th) and multiply by 3, then add the digits in even-numbers positions to that product, the total will always be congruent to 0 mod 10:

Try this for yourself, especially if you weren’t in class today.

This feature is an example of a “checksum,” a scheme for verifying correctness of a group of numbers by requiring that something based on their sum is congruent to some constant modulo some other constant — different checksum systems use different constants, “sum” functions, etc. Barcodes were designed with a checksum to detect scanner errors (e.g., if a piece of dust blocks a sensor during a scan); the Internet also uses checksums to ensure that blocks of data (e.g., your latest email) haven’t been corrupted in transit; etc.

Proofs

(From Progress Check 3.2 in our textbook.) Prove that if a, b, and c are integers such that a|b and a|c, then a|(b+c).

The key thing in this proof is to recognize how to bring in and use the definition of divisibility. We did that in a proof that we wrote formally, using LaTeX. The source document and output file are both available from Canvas.

Prove that if a and b are integers such that a ≡ 2 (mod 3) and b ≡ 2 (mod 3), then (a+b) ≡ 1 (mod 3).

We didn’t have time to write this as a formal proof, but we did outline the main ideas. Once again, seeing where to bring in the definition of congruence, combined with seeing how to do some algebra following it, are probably the crucial things.

Working forward and backwards, as in know-show tables, can be helpful for identifying the algebra you need to do. Specifically, the definition of congruence told us that at the beginning, 2 - a = 3k, and 2 - b = 3n, for some integers k and n, and that at the end we want to see 1 - (a+b) = 3m for some integer m; the middle part of the proof thus needs to rearrange 2 - a = 3k and 2 - b = 3n into 1 - (a+b) = 3m.

The key ideas in how we did that are:

1. From the definition of congruence, 3 | (2-a), i.e., 2 - a = 3k for some integer k
2. Similarly, 2 - b = 3n for some integer n
3. Now we want to show that 1 - (a+b) = 3m for some integer m
4. Maybe we could use what we know about a and b to work out what a+b is, then subtract that from 1:
   1. 2 - a = 3k means a = 2 - 3k, and 2 - b = 3n means b = 2 - 3n
   2. So a + b = 2 - 3k + (2 - 3n) = 2 - 3k + 2 - 3n = 4 - 3k - 3n
   3. 1 - (a+b) = 1 - (4 - 3k - 3n) = 1 - 4 + 3k + 3n = -3 + 3k + 3n = 3(k+n-1)
5. Now, since integers are closed under addition and subtraction, we have 1 - (a+b) is divisible by 3, as we wanted!

Next

Proving statements using their contrapositives.

Please read “Beginning Activity 1 (Using the Contrapositive),” “Review of Direct Proofs,” “Proof Using the Contrapositive,” and “Writing Guidelines” in section 3.2 of the textbook.

Please also participate in this discussion of the contrapositive.

Remember that I will be at a conference Monday (and Tuesday) next week. The discussion is therefore essentially an asynchronous substitute for Monday’s class. As such, it has something to turn in! In particular, the discussion’s goal is for you to cooperate through it to collectively create a proof, and I want you to bring your own summary of that proof to your next grading meeting with me.

Even though I’ll be conferring, I expect to be able to keep an eye on the discussion and participate if needed.

Next Lecture