Modular Congruence

Return to Course Outline

Previous Lecture

Problem Set

About proof by contradiction and cases. See handout for details.

Questions?

Hints about proving the corollary in Problem 4 from the current problem set?

The corollary is that for all real numbers x and y, if x < y then there exists a natural number n such that x < x + 1/n < y.

The key insight is to realize that because x < y, y - x > 0, and so the proposition from earlier in Problem 4 applies to it. In particular, there exists a natural number n such that 0 < 1/n < y - x. Then add x to each part of the inequality.

The Division Algorithm

From section 3.5

Magically Predicting Bar Codes

Give me the first 11 digits of a UPC bar code and I will predict the last digit.

The trick is that the digits in a bar code have a pattern. Namely, if the digits are identified from left to right as x₁, x₂, x₃, and so forth up to x₁₂, then

3x₁ + x₂ + 3x₃ + x₄ + 3x₅ + ... + 3x₁₁ + x₁₂ ≡ 0 (mod 10)

This gives an equation that can be solved for any single digit that is missing.

(The real reason for this rule is to allow errors due to mistyped human entry or mis-scanned automatic reading to be detected, namely if the digits entered or read don’t satisfy the above equation. Schemes such as this are called “checksums.”)

The Basic Claim

Try the bar code “magic” for yourselves.

Key Points

You can save yourself work by mentally keeping track of the “r” value from the Division Algorithm for sums of digits, products, etc. as you calculate, rather than keeping full sums, products, etc. That this is equivalent to keeping full sums etc., and then finding r at the end follows from theorems proved in the reading.

Congruence and Proof by Cases

Also from section 3.5.

Example

A simplification of a conjecture from the discussion of bar codes: is it true that for all k ≢ 0 (mod 4), 3k ≢ k (mod 4)?

Analyze the claim by cases (if the claim is true these cases will be the nucleus of a proof by cases, if the claim is false these cases provide a systematic way to find a counter-example)

1. k ≡ 1 (mod 4): 3k ≡ 3×1 (mod 4) ≡ 3 (mod 4)
2. k ≡ 2 (mod 4): 3k ≡ 6 (mod 4) ≡ 2 (mod 4). So here’s a counter-example to the conjecture.
3. k ≡ 3 (mod 4) 3k ≡ 9 (mod 4) ≡ 1 (mod 4).

Next

Introduction to proof by induction.

Read section 4.1.

Next Lecture