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

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

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,

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.

-----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

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