SUNY Geneseo Department of Mathematics
Monday, March 22
Math 239 03
Spring 2021
Prof. Doug Baldwin
(No.)
I’ve looked at the mid-semester feedback surveys. There were only a few suggestions for changes, in particular
Otherwise they mentioned things to keep doing, all of which I like and plan to continue, including
Based on section 3.5 in the textbook and this discussion of modular congruence.
This is part of understanding how arithmetic works when numbers and results are treated “mod n,” i.e., as the remainders described by the division algorithm. For example, all computer arithmetic is modular, with the moduli being various powers of 2.
Theorem: If a, b, c, and d are integers, and n a natural number, such that a ≡ b (mod n) and c ≡ d (mod n), then (a+c) ≡ (b+d) (mod n)
Proof: The finished formal proof is in LaTeX, with the source file and PDF output available in Canvas. But how we arrived at that proof is also interesting:
We started by using the definition of congruence to recognize that a ≡ b (mod n) means that n divides a - b, i.e., a - b = kn, and c ≡ d (mod n) means c - d = mn, for some integers m and n.
Then we turned to a “know-show” view, and asked where we want to go from those facts. We eventually realized that applying the definition of modular congruence to (a+c) ≡ (b+d) (mod n) means we want to get that (a+c) - (b+d) = pn for some integer p.
Someone suggested that from a - b = kn and c - d = mn, we can get a - b - kn = 0 = c - d - mn, and so setting a - b - kn = c - d - mn gives us an equation involving all the relevant variables; rearranging gives a - b - c + d = kn - mn, or (a-c) - (b-d) = (k-m)n, which is almost what we want. But not seeing a way to get exactly what we wanted from it, we backtracked and tried another tack, namely adding the equations a - b = kn and c - d = mn, as seen in the finished proof.
Two morals from this for proof-writing in general are (1) have a sense of what you need to get to, and (2) be willing to try new ways of getting there if one gets stuck.
(See the March 5 and March 19 classes for the UPC bar code checksum rules.)
If I’m trying to reconstruct a missing digit from a bar code, can I be certain there is a unique solution? In particular, if I’m trying to solve an equation of the form c + 3d ≡ 0 (mod 10), where d is the missing digit and c is the known (weighted) sum of the other digits, can I be sure there’s only 1 value of d between 0 and 9 that will solve the equation?
You can, and the “proof” (not really a formal one this time) is a case analysis based on the remainder when c is divided by 10 (i.e., the remainder guaranteed by the division algorithm). The analysis is tedious because there are 10 cases, and we didn’t write it all out, but the idea is simple.
Case 0: c ≡ 0 (mod 10), d = 0 works, other possible d values don’t. d = 0 is unique!
Case 1: c ≡ 1 (mod 10), d = 3 works (since 3×3 = 9), other values of d don’t.
Continuing on similarly shows that there is a unique solution for each possible remainder for c.
So this is a nice reminder/example of proof by cases.
Induction (our last proof technique).
Please read “Beginning Activity 1,” “Beginning Activity 2,” and “Inductive Sets” in section 4.1 of the textbook.
Please also participate in this discussion of inductive sets.