Thursday, April 4, 2013

Discrete Math - Day 41

Today we continued looking at problems related to the Chinese Remainder Theorem. The first problem comes from an Indian text dating back 1,400 years. In this problem, students are told the number of eggs leaves a remainder of 1 when divided by 2, 3, 4, 5, and 6. The number of eggs is evenly divisible by 7.

I have to admit that the lack of strategies used by students is of concern to me. I am not sure why, perhaps being the first week back from break or being the first class of the day, but whatever the cause, students are not working smartly.

For this problem, most students were simply guessing at values in a non-systematic manner. When I asked them how they could make use of the information given in a problem they couldn't think of anything that might be effective. I told the class they could make use of the fact that the number of eggs was divisible by 7. Many simply started guessing at which multiple of 7 may work.

One group started working through every multiple of 7 without considering the information provided for other values. This group continued looking at every multiple of 7 until they got to 301 and found it worked. They did not consider that multiples of 7 involving the primes 2, 3, 5 could be ignored. This meant the could simply look at all values 7p where p is a prime number, p > 5. It turns out that 301 = 7 x 43. A few students appreciated this connection and use of information, but most did not.

I asked the class to consider what we did to generate an equation that would provide all possible solutions to the Fred's Baseball Card problem from last class. This again was a struggle. I revisited the equation that was derived: B(x) = 84x + 49. I asked where the 49 came from. The class recognized that this was the smallest amount of cards that satisfied the problem's conditions. When I asked where the 84 came from I drew blank stares. I asked the class what relationship did we find between the given prime numbers and 84. Finally, someone said that 84 was the smallest number that could be divided by 2, 3, 4, and 7. I rephrased that statement to say that 84 was the least common multiple of 2, 3, 4, and 7. This provided enough information for students to create the equation E(x) = 420x + 301.

I then showed the class another problem that came from a Chinese text dated to around 250 CE. In this problem the value being sought leaves a remainder of 2 when divided by 3, a remainder of 3 when divided by 5, and a remainder of 2 when divided by 7. As with the previous problem, students simply started making guesses rather than using the given information.

I asked students to make use of the fact that when dividing by 7 you were left with a remainder of 2. Students struggled with how to create that list. I pointed out that 9 divided by 7 produced a remainder of 2. The response was, "But 9 doesn't work." I prodded them as to what other values will leave a remainder of 2. They finally started producing a list and some found that 23 met the problem's conditions.

One group stumbled upon the value 128 and found that it worked. I asked them if this was the smallest value that worked. I reminded them that the LCM would come into play. They found the LCM for 3, 5, and 7 was 105. Subtracting this from 128 yielded 23.

Students were more readily able to express the equation T(x) = 105x + 23 that produces all solutions for the problem's conditions. Overall, I saw students struggling with how to determine a LCM, how to make use of a problem's given conditions, and how to derive an equation from the patterns produced. It was quite disheartening.

I summarized the idea of the Chinese Remainder Theorem:

Any system of linear congruences  has a unique solution (s) such that

  • 0 < s < LCM(divisors)
  • the difference between any two solutions is divisible by LCM(divisors)
  • dividing any other solution r > s by LCM(divisors) produces a remainder of s.

We only had about 15 minutes remaining and given the productivity I'd seen so far, I decided to show the initial clip of the video The Music of the Primes. This segment discusses prime numbers and recaps Euclid's proof that there are infinitely many primes. It had a nice connection as the video also made use of the number 105 to illustrate that it was the product of the primes 3, 5, and 7.

It does give students pause to consider that some 2,500 years ago, ancient Greeks were considering questions about prime numbers.

Tomorrow students will consider the relationship between the greatest common divisor and the least common multiple. I am away at a math competition, so it will be interesting to hear how things go.

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

No comments:

Post a Comment