To begin class, I asked them if 49 was the smallest composite number that was relatively prime to 30? There was some discussion and one student explained that because 30 = 2 x 3 x 5, the next available prime number that could be used was 7 and that 7 x 7 would be the smallest composite number that could work.
To check for understanding, I asked students what would be a composite number that was relatively prime to 210. While not everyone got the idea, students came up with values like 169 = 13 x 13 and 121 = 11 x 11. For others, I asked them to look at their prime number sheet and see what prime numbers were available to use. The conclusion was that 121 was the smallest composite number relatively prime to 210 since 11 was the next available prime number to use.
The definition of relatively prime was extended to all positive integers so that positive integers n and m are relatively prime if gcd(n, m) = 1. This applies to both prime numbers and composite numbers. The class discussed the implication for two distinct prime numbers--they will be relatively prime. The class verified their understanding by identifying pairs of relatively prime numbers.
Euler's totient function was introduced. This function counts the number of integers that are less than or equal to n and are relatively prime to n. The totient function is designated using the Greek letter phi, that is φ(n).
For example, what does φ(4) equal? In this case, the integers ≤ 4 are {1, 2, 3, 4} and both gcd(1,4) and gcd(3,4) equal 1. Therefore, φ(4) = 2.
Students created a list of φ -values for all integers from 1 through 20. There was some confusion and hesitation at first but by answering their questions and verifying their first attempts they were off and running. The class then verified their results. A couple of values presented by one student were questioned and the class came to a consensus about what each value should be.
I asked the class to look at their results and think about any patterns that they made use of in creating their list of φ-values. Students mentioned that when working with even numbers they were able to immediately eliminate all the even values less than n. They also noticed that for any prime number p, φ(p) = p - 1.
Additionally, students saw that all the φ-values were even except for φ(1) = 1 and φ(2) = 1. One student conjectured that for n > 1, φ(2n) ≤ n and φ(2n + 1) > n. This presented the opportunity to discuss how mathematicians make observations like these and then try to determine the truth of these conjectures. I didn't want to dive into trying to prove the conjecture right at that moment. We will explore some additional properties of the totient function that will enable the class to more easily answer this question.
I asked the class to explore the multiplicative nature of the totient function, that is
when does φ(n x m) = φ(n) x φ(m) for positive integers n and m?
Students explored different examples using their list of values for the integers 1-20. In doing this they noticed several things:
- the multiplication doesn't work when n and m are both even
- the multiplication doesn't work when n = m, i.e. for square numbers
- the multiplication may or may not work for a given integer
One student decided to test the square number conjecture by finding φ(25) and comparing it to φ(5) x φ(5), which demonstrated that they were not equal.
This last one was intriguing. Students found φ(18) = φ(9)φ(2) but that φ(18) ≠ φ(3)φ(6) and, similarly,
φ(24) = φ(3)φ(8) but that φ(24) ≠ φ(4)φ(6). The question is why? What is different in the values being multiplied that enables one product to be true while the other is not for the same integer?
Students pondered this for a while and someone conjectured that perhaps it was because in one instance the two integers had a common factor, causing the product to not work, while in the other instance the two integers did not have any common factors.
Putting this back in terms of relatively prime numbers the conjecture became φ(n x m) = φ(n) x φ(m) if gcd(n,m) = 1. The class explored this conjecture and decided it was true. The result was verified. The big question is why?
Students wrestled with this idea. As I walked around I asked them to consider what went into determining each φ-value. Students got to the idea that the common factors were somehow affecting the result. We looked explicitly at φ(24) = φ(3)φ(8) and φ(24) ≠ φ(4)φ(6). In the latter situation, the values 2 and 4 are eliminated from both lists as you go through and determine relative primes. In the first situation, this does not happen. I left it at this informal level as we will be exploring the totient function further.
To conclude the class, I had students do a brain dump in their notes of their thoughts about factoring, relative primes, and the totient function. I asked them to also record questions they had about what we've been doing. This process helps to students to start organizing their thoughts and to explicitly connect different pieces.
Tomorrow we'll explore additional ideas around the totient function that will lead to Euclid's algorithm.
φ(24) = φ(3)φ(8) but that φ(24) ≠ φ(4)φ(6). The question is why? What is different in the values being multiplied that enables one product to be true while the other is not for the same integer?
Students pondered this for a while and someone conjectured that perhaps it was because in one instance the two integers had a common factor, causing the product to not work, while in the other instance the two integers did not have any common factors.
Putting this back in terms of relatively prime numbers the conjecture became φ(n x m) = φ(n) x φ(m) if gcd(n,m) = 1. The class explored this conjecture and decided it was true. The result was verified. The big question is why?
Students wrestled with this idea. As I walked around I asked them to consider what went into determining each φ-value. Students got to the idea that the common factors were somehow affecting the result. We looked explicitly at φ(24) = φ(3)φ(8) and φ(24) ≠ φ(4)φ(6). In the latter situation, the values 2 and 4 are eliminated from both lists as you go through and determine relative primes. In the first situation, this does not happen. I left it at this informal level as we will be exploring the totient function further.
To conclude the class, I had students do a brain dump in their notes of their thoughts about factoring, relative primes, and the totient function. I asked them to also record questions they had about what we've been doing. This process helps to students to start organizing their thoughts and to explicitly connect different pieces.
Tomorrow we'll explore additional ideas around the totient function that will lead to Euclid's algorithm.
Visit the class summary for a student's perspective and to view the lesson slides.
No comments:
Post a Comment