Discrete Math - Day 46

Today we continued looking at solving systems of linear congruences.  Class started by my addressing some of the questions students wrote down last class.

The first question dealt with how many times could the same numbers be congruent. This question indicated some confusion between the idea of a single congruence versus a system of congruence. I tried to clarify this by pointing out that two values either are or are not congruent modulo a third value. In a system of linear congruences, a linear equation describes the solution set and every value of that form fits the criteria, so there are an infinite number of solutions.

The second question asked about extending transitivity to additional values. This was a good projection from the student and I confirmed that repeatedly applying the third congruence property guarantees that transitivity extends to as many values as you want.

Another students wondered why do the proofs given actually prove the congruence properties. Looking through the work that students produced, it was evident that they are struggling with proof. As this is the first time that students have had to work with proofs this is understandable.

I told the class that all a proof was was using known properties and generally accepted techniques combined with a structured, logic argument to reach a conclusion. For the congruence property proofs, we started with a stated definition, used generally accepted algebraic rules for integers to step through to a logical conclusion that the property was true.

I told the class it was okay that they may be struggling with where to start or how to proceed with a proof. The difficulty is for students to structure their reasoning and logic so that it flows from one step to the next.

The last question asked how do you solve systems of linear congruences. This was the topic for the lesson, although I may re-think this lesson. I will look at how much this process is actually needed in the work we will undertake.

The lesson revisited the Chinese remainder problem. The problem was re-written as a system of linear congruences.

1. x ≡ 2 (mod 3)
2. x ≡ 3 (mod 5)
3. x ≡ 2 (mod 7) 

I asked the class what the first statement told us about the relationship among x, 2, and 3? After some thought, a student said that x - 2 is a multiple of 2. I wrote down x - 2 = 3k₁. We can use this to give us x = 3k₁ + 2.

And now this is where things start to get messy.

Use equation 2 and substitute the expression 3k₁ + 2 for x. The result is 3k₁ + 2 ≡ 3 (mod 5), or 3k₁ ≡ 1 (mod 5), using congruence property 2.

We have that 6 ≡ 1 (mod 5). Using congruence property 3 we now have 3k₁ ≡ 6 (mod 5). Re-writing the value 6 as 2 x 3, we see that 3k₁ ≡ 2 x 3 (mod 5). Using congruence property 1 we end up with k₁ ≡ 2 (mod 5).

We repeat the process using the relationship k₁ ≡ 2 (mod 5). This means 
k₁ - 2 = 5k₂, or k₁= 5k₂ + 2 and through substitution

x = 3k₁ + 2 = 3(5k₂ + 2) + 2 = 15k₂ + 8. Substitute this value into the third expression, so that
15k₂ + 8 ≡ 2 (mod 7) and repeat the process.

15k₂ + 8 ≡ 2 (mod 7) means that 15k₂ ≡ -6 (mod 7) but 1 ≡ -6 (mod 7) and 1 ≡ 15 (mod 7). The result is 15k₂ ≡ 15 (mod 7). Again, using congruence property 1, we see that k₂ ≡ 1 (mod 7). Writing out the result shows that k₂ = 7k₃ + 1. Substituting for our x expression we know have 
x = 15k₂ + 8 = 15(7k₃ + 1 ) + 8 = 105k₃ + 8.

This is the equation that was found when the class first worked on this problem. Needless to say, student heads were spinning as they tried to work through the process and algebraic manipulation. As I told students, for any problem they know how to find the slope for the solution set, since it is simply the least common multiple of the modulus values. The issue is finding the starting value. For this problem, the upper bound is 105 and there are only a few multiples of 7 that need to be checked. For the broken egg problem, a process like this would be quicker.

I asked students to attempt to use this process on the Fred's Baseball Card problem. I'll see how they fared but I'm thinking that I don't want to belabor this procedure. I know we'll need to look at equivalent congruence values that come up in this process, but it may be that focusing on modular arithmetic and the corresponding addition and multiplication tables may be all that is needed.

Modular arithmetic is actually the next topic and I think a day spent there will be more productive than spending another day on this process. I may eliminate this piece altogether for the next time.

Visit the class summary for a student's perspective and to view the lesson slides.