A few students thought the proof might be similar to what we did for addition. Their reasoning was that multiplying is a similar operation to addition. When we multiply the values the quotient increases but when we take the differences, the remainders will cancel each other.
The idea of abstraction is a stretch for students as they are conditioned to work with specific examples and do not have experience generalizing results. The class is starting to appreciate the difference between many demonstrations versus a proof. In the former, you provide strong evidence of a truth while with the latter you demonstrate the truth for all situations under the given conditions.
I provided a think-a-loud of the proof to help students along.
Congruence Property 3:
If a ≡ b (mod m) and c ≡ d (mod m) then ac ≡ bd (mod m), for any integers a, b, c, and d and positive integer m.
PROOF
The if statement provides a starting point, specifically that we assume a ≡ b (mod m) and c ≡ d (mod m). From the definition of congruence we have that (a - b) = km and (c - d) = lm. From the result we are trying to prove I will need to demonstrate that ac - bd is a multiple of m. I can see that I will need to have value ac and bd. Looking at what I can start with, I'll take the simplest approach I can an multiply (a - b) = km by c, resulting in ac - bc = kcm. This is making use of Congruence Property 1, which was covered last class. We can do something similar with our second given congruence to obtain a bd value, that is bc - bd = lbm. Now, I can certainly add kcm and lbm together. This means I can add their respective representations together, so we obtain kcm and lbm = (kc + lb)m = ac - bc + bc - bd = ac - bd. This shows that ac - bd is a multiple of m. By definition, ac ≡ bd (mod m). Q.E.D.
After going through this, many students were still uncertain, although they asked some pertinent clarifying questions and could follow the logic involved.
We next looked at powers of values, that is, if a ≡ b (mod m) what happens for
an ≡ bn (mod m)? Students explored this relationship using the values they worked with from the last class. The class saw that this appeared to work.
I asked students to consider how they could demonstrate the truth of this statement. Most students struggled with this but one group thought that since a - b was a multiple of m, that as you raised a - b to a power, that power would still have to be a multiple of m. This is precisely the approach that is taken to prove this result. I provided a slightly more formal presentation of this idea after the students presented their idea. This provided our final congruence property.
Congruence Property 4:
If a ≡ b (mod m) then an ≡ bn (mod m), for any integers a and b and positive integers n and m.
It appears from all of these properties that congruence relations act similar to equality relations. From these first four congruence properties we have behavior that mirrors basic arithmetic for integers. It is this idea of arithmetic using congruence relations that we will make use of to solve linear congruence relations and to incorporate in cryptography.
The last piece to more formally demonstrate the similarity between congruence and equality relations is to show that congruence relations form an equivalence relation. To do this, three properties must be shown to be true.
Congruences form an equivalence relation. That is
- Reflexivity: a ≡ a (mod m)
- Symmetry: if a ≡ b (mod m) then b ≡ a (mod m)
- Transitivity: if a ≡ b (mod m) and b ≡ c (mod m) then a ≡ c (mod m)
I asked students to use the definition of congruence and the congruence properties we proved to demonstrate that these three properties hold. There was about 15 minutes left in class and I told students I would collect their work to see where they were on proving statements.
Most students were stuck on how to start. As I walked around, I asked students what they knew about the first statement and what they were trying to demonstrate. Invariably they would say that they needed to show that a left the same remainder as a when dividing by m. They then would have this surprised look on their faces and say, "Oh, that's obvious." I would ask them to consider the formal definition of congruence and to consider if (a - a) is a multiple of m. At first they would think no, because a - a = 0. Then they would realize that 0 = 0 x m, so a - a is a multiple of m.
For the second statement, some students struggled with the role reversal. I would use their specific examples and ask what would happen if the values were switched. They soon realized they were obtaining the negative difference. This meant that (a - b) = -(b - a). So if (a - b) is a multiple of m then b - a is the negative multiple of m.
There were more struggles for the third property. One student started to take the approach used in proving Congruence Property 3. This led to the result that a - b = km and b - c = lm. Adding km and lm together yields km + lm = (k + l)m = a - b + b - c = a - c. This means that a - c is a multiple of m and therefore a ≡ c (mod m).
I asked students to include any questions on their paper and collected the results. I will be interested to see student attempts on proving these three relations. Although they are not difficult in and of themselves, these are challenging ideas for students who have little or no experience with proof.
As I explained to the class, we have laid a mathematical foundation for using congruence relations much like we use equality relations. The next class, we'll use this foundation to look at a more formal way to solve systems on linear congruences.
Visit the class summary for a student's perspective and to view the lesson slides.
No comments:
Post a Comment