November 22 Summary
We did talk a while about the first unexam. I want to stress that this
is not supposed to be an exercise about counting or doing counting
problems, it is all about the writing. I want you to explain something
from first principles including only sentences which you need in order to
explain the solution. It will be due on December 6, 2007.
Next we talked about the Euler phi function, phi(n).
I said it was easy to show that for gcd(p,n)=1, p prime
phi(p^a n) = (p^a - p^(a-1)) phi(n)
But then I spent about a half hour trying to explain why that is true.
I said, consider the set of elements which are between 1 and p^a n such that
have gcd(k,n) =1. By the division algorithm k = q n + r where 0 ≤ r < n and
0 ≤ q < p^a and if gcd(k,n)=1 then we must have gcd(r,n)=1. That is,
(first set) = { k : gcd(k,n)=1, 1 ≤ k < p^a n } =
{ q n + r : 0 ≤ q < p^a, 0 ≤ r < n, gcd(r,n)=1 }
From these elements we want to subtract off those such that gcd(k,p) > 1. That is
we remove the subset of integers
(second set) = { p q n + p r : 0 ≤ q < p^(a-1), 0 ≤ r < n, gcd(r,n)=1}
because every integer in the first set that contains a factor of p will look like this.
Now how many choices are there for q and r? In the first set 0 ≤ q < p^a, so
q has p^a choices
and r has phi(n) choices. In the second set q has p^(a-1) choices and r still has phi(n) choices.
Therefore the number of elements in the first set which are not in the second are
p^a phi(n) - p^(a-1) phi(n)
It follows roughly immediately that phi(n) is "multiplicative" since
if m = p1^a1 p2^a2 ... pk^ak and n is relatively prime to n then
phi( m ) = (p1^a1-p1^(a1-1)) phi( p2^a2 ... pk^ak)
= (p1^a1-p1^(a1-1)) (p2^a2-p2^(a2-1)) phi( p3^a3... pk^ak)
= ...
=
(p1^a1-p1^(a1-1)) ( p2^a2 - p2^(a2-1)) ... (pk^ak - pk^(ak-1))
and moreover
phi( mn ) = (p1^a1-p1^(a1-1)) phi( p2^a2 ... pk^ak n)
= ...
=
(p1^a1-p1^(a1-1)) ( p2^a2 - p2^(a2-1)) ... (pk^ak - pk^(ak-1)) phi(n)
= phi(m) phi(n).
Next we talked about sequences in general. We have several example of sequences which
represent the number of "things in a set."
* the number of integers between 1 and n relatively prime to n = phi(n)
* the number of divisiors of n = d(n)
* the number of subsets of size 3 of a three element set = C(n,3)
* the number of orderings of the numbers 1 through n = P(n,n) = n!
I can go on, these are just a few that we have explicitly encountered so far in
this class. Some of the homework problems have involved others.
Now consider an abstract sequence of numbers where the i^th element in the sequence
represents the number of something of "size" i.
a_0, a_1, a_2, a_3, a_4, ...
I call these somethings widgets, to
represent an unknown object so that the number a_i represents the number of widgets
of size i. Then I said to make things interesting we can also talk about another
sequence of non-negative integers which represents the number of doodles of size i.
b_0, b_1, b_2, b_3, b_4, ...
Then I asked what does the expresson
a_3 b_7 + a_1
represent? I suggested it was the number of widgets of size 1 or
the number of ways of taking a widget of size 3 and tying it to a
doodle of size 7 with rubber bands. We then did a worksheet
together in class with exercises of this sort.
-----Added later because someone asked for a better explanation of this worksheet. ------
It is easier to go from the lettered descriptions to the numbered expressions than the other
way around.
for example, the first one is:
(a) A pair consisting of a widget and a doodle such that the doodle is of size less than or equal to n and itÊ
is one size larger than the widget
By a pair I mean and ordered tuple consisting of two elements.
the doodle of size 1 through n (it can't be 0 because there are no widgets of size -1).
If the doodle is of size k then the widget is of size k-1 and there are a_{k-1} b_k such pairs.
By the addition principle there are
a_0 b_1 + a_1 b_2 + ... + a_{n-1} b_n
such pairs
(since either the doodle is of size 1, or it is of size 2, or ... or it is of size n).
This matches with (13).
I will try posting the answers to this worksheet here later,
but you should try to do them yourself first.
-Mike