Final exam with answers

Here.

Answers to practice problems

1a. Let a,b be natural numbers, a < b. Assume there exist x,y in the naturals such that xa + yb = gcd(a,b). Show y < 10.

A. It depends on whether a=0 or a>0.

If a=0, then the gcd is b. x doesn't matter, and y must be 1. 1 < 10, huzzah.

If a>0, then the largest the gcd can be is a. On the other hand, the smallest positive number that xa+yb can be is a. So both must be a. Hence x=1, y=0. 0 < 10, huzzah redux.

b. Give an example where x > 10.

A. Apparently we're in the a=0 case, since otherwise x would have to be 1.
So y must be 1, and x and b are free to roam. Take x = 57 and b = 1066, for example.

2. What are the last two decimal digits of 11²⁰⁰⁸?

A. 81.
More generally, 11ⁿ == 10n + 1 mod 100.
This is easy to prove by induction: multiply both sides by 11, obtaining
11ⁿ⁺¹ == 110n + 11 == 10n + 11 == 10(n+1) + 1 mod 100.

3a. Draw an example of finite sets X,Y,Z and functions f:X->Y, g:Y->Z where |X| > |Y|, f is not onto, but the composite g o f is onto.

A. Say X = {a,b,c}, Y = {taupe,vermilion}, Z = {cheese}. Let f(x) = taupe for any x, and g be the only function Y->Z.

b. Prove that |Y| is not equal to |Z| (not just in your example, but in any example).

A. Since g o f is onto, the map image(f) -> Z (made by restricting g) is also onto.
Hence |Z| is less than or equal to |image(f)|. Since image(f) is contained in Y, |image(f)| is less than or equal to |Y|. But f is not onto, so it's strictly contained. Hence |image(f)| < |Y|.


4. In each of the following: can you turn the following two congruences into one, and if so, what?

v1. b congruent to 2 mod 6, b congruent to 7 mod 10.

A. No you can't; the first says b is even, the second says it's odd.
Whereas any single congruence does have solutions.

v2. b congruent to 1 mod 6, b congruent to 7 mod 10.

A. The first can be rewritten as "b congruent to 7 mod 6". Hence 6 and 10 divide b-7, or equivalently, 30 divides b-7. So they can be rewritten as e.g. b-2 congruent to 5 mod 30.

5. Say b == a+7 mod 27, and a² == b² mod 27.
Figure out a,b mod 27.

A. a² - b² == 0 mod 27.
So (a+b)(a-b) == 0 mod 27.
So (a+b)(-7) == 0 mod 27.
Since gcd(7,27) = 1, we can cancel the 7.
So a+b == 0 mod 27.
So 2a+7 == 0 mod 27.
How to cancel the 2? Subtract 27 from both sides, for example; 2a-20 == 27 == 0 mod 27.
So a-10 == 0 mod 27. Hence a == 10 mod 27, b == 17 == -a mod 27.

109 roundup

Definitions.
Quantifiers.
Proofs. Case check, contradiction, induction, series of reductions.
Make sure during induction that the chain of implications isn't broken anywhere.
To prove sets are equal, show both inclusions.
To prove functions are equal, check them on every element.
Functions; 1:1, onto, invertible.
Baby number theory. The division algorithm, Euclid's algorithm, the fact that the gcd can be written as an integer linear combination of the two numbers, unique factorization into primes. Congruences. Chinese Remainder Theorem.
Partitions and equivalence relations.
(n choose k) and the Pascal recurrence for it.

Office hours

I'll be in my office (7450 APM) Tuesday 11-4 and Wednesday 11-2. I'll be giving preference to my Math 109 students on Tuesday and my Ma 20b students on Wednesday, but anyone will be welcome any time.
If you want to call ahead to check "Are you already tied up with the other class?", feel free; my office number is 858-534-6450.
(Don't get 7450 and 6450 confused!)

Practice problems for the final

I'm having some writer's block coming up with extra problems, but I'll keep working at it. Here are three so far. (As usual, it's trickier than what's actually on the final.)

1a. Let a,b be natural numbers, a < b. Assume there exist x,y in the naturals such that xa + yb = gcd(a,b). Show y < 10.

b. Give an example where x > 10.

2. What are the last two decimal digits of 11²⁰⁰⁸?

3a. Draw an example of finite sets X,Y,Z and functions f:X->Y, g:Y->Z where |X| > |Y|, f is not onto, but the composite g o f is onto.

b. Prove that |Y| is not equal to |Z| (not just in your example, but in any example).

4. In each of the following: can you turn the following two congruences into one, and if so, what?

v1. b congruent to 2 mod 6, b congruent to 7 mod 10.

v2. b congruent to 1 mod 6, b congruent to 7 mod 10.

5. Say b == a+7 mod 27, and a² == b² mod 27.
Figure out a,b mod 27.

Answers to HW #6

1. What are all the partitions of {1,2,3,4}?

A. Organized by the number of cells:
With 1 cell, there's just {{1,2,3,4}}.
With 2 cells, their sizes could be 1+3 or 2+2. There are four of the first type, like {{2},{1,3,4}}, and three of the second, like {{1,3},{2,4}}.
With 3 cells, the only way to break them up is 2+1+1. There are (4 choose 2) of these, like {{2,4},{1},{3}}.
With 4 cells, there's just {{1},{2},{3},{4}}.
In all, 1+4+3+6+1 = 15.

2. Let PowerSet(X) denote the set of subsets of X, and Partitions(X) denote the set of partitions of X. Let f:X->Y be a function from X to Y.

a. Define a function (properly called PowerSet(f)) from PowerSet(X)->PowerSet(Y), in a nontrivial way. Once you've found the right one, you should be able to prove that if f is injective, then PowerSet(f) is too; do prove this.

A. If S is a subset of X, define PowerSet(f) (S) = {f(x) : x in S}.
Sometimes this is denoted f(S), by the way.

To show this is injective, let S,T be two subsets of X, and assume PowerSet(f)(S) = PowerSet(f)(T). Then for all s in S, f(s) is in PowerSet(f)(S), so f(s) is in PowerSet(f)(T), so there exists t in T such that f(s) = f(t). But then s = t, since f is assumed 1:1. This shows that S is a subset of T. The same argument works to show T is a subset of S. So they are equal.

b. Also, if f is surjective, show that PowerSet(f) is too.

A. Let T be a subset of Y, and let S = f^-1(T). Then I claim that PowerSet(f)(S) = T,as follows. An element y of Y is in PowerSet(f)(S) iff there exists s in S such that f(s) = y. By our definition of S, such a y must be in T. So far this shows that PowerSet(f)(S) is contained in T.
To show the opposite inclusion, we use the fact that f is onto: for any t in T, there does indeed exist s in f^-1(T) such that f(s)=t.


c. Define a function (properly called Partitions(f)) from Partitions(Y)->Partitions(X) -- it goes backwards! Once you've found the right one, you should be able to prove that if f is surjective, then Partitions(f) is injective; do prove this.

A. Given a partition P of Y, there is a natural surjection Y ->> P. Compose the maps X -> Y -> P and define Partitions(f)(P) to be the partition of X induced by the map X -> P.

Given a partition Q of X, we can almost make a partition P of Y; let P = {f(S) : S in Q}.
It is easy to check that the subsets f(S) of Y are disjoint and nonempty; the only worry is that they may not cover Y. But if f is onto, then they do.
It is also easy to check that if we start with a partition of Y, build a partition of X as above, and then build a partition of Y as just described, we get back where we started. That shows that Partitions(f) is injective.

d. Also, if f is injective, show that Partitions(f) is surjective.

A. Let Q be a partition of X, and let P' = {f(S) : S in Q}.
This isn't quite a partition of Y, as explained above; it may not cover Y.
So let P = P' union { Y \ image(f) }, i.e. add an extra cell containing the rest of Y.
Then it is easy to see that Partitions(f)(P) = Q.

3. Let X be a subset of Y, where Y is finite. How many subsets of Y contain X? Give (and explain) a formula in terms of |X|, |Y|.

A. The subsets of Y containing X correspond in an obvious way to the subsets of Y \ X,
of which there are 2^{|Y \ X|} = 2^{|Y| - |X|}.

4. Let f(x) be a polynomial of degree m. Show that f can be written as a linear combination of the polynomials {x choose k} for k=0,1,...,m. (I shouldn't need to say it, but hint: induction.)

A. Let C be the coefficient of x^m in f(x). Then f(x) - C m! {x choose m} is a polynomial of degree at most m-1. If m=0, we're done; otherwise we use induction on m to say that f(x) - C m! {x choose m} is a linear combination of {x choose k} for k=0,1,...,m-1. Add on C m! {x choose m} to that combination, and we get the desired conclusion.

5a. Say f(x) = sum_k=0^m c_k x^k/k!.
Give a formula for the polynomial f'(x).

A. f(x) = sum_k=0^m-1 c_k+1 x^k/k!.
This takes a couple of steps; first compute the derivative, then notice that we can drop the k=0 term because it's 0 anyway, then shift k by 1.

b. Say f(x) = sum_k=0^m c_k {x choose k}.
Give a formula for the polynomial f(x+1)-f(x).

A. f(x+1) - f(x) = sum_k=0^m-1 c_k+1 {x choose k}.
This is proved using the Pascal recurrence {x+1 choose k} - {x choose k} = {x choose k-1}. After that do the same as in part (a).

c. Use (b) to prove that a polynomial f(x) takes on integer values for every integer x if and only if it is an integer combination of {x choose k}s.
(So we come full circle: one of the first things we proved was that {x choose 2} is such a polynomial.)

A. Since the {x choose k} take on only integer values (at x integer), if the (c_k) are all integer then f(x) will only take on integer values too. That's the easy direction.

Now assume that f(x) only takes on integer values. Hence f(x+1) - f(x) is also always integer. We calculated it a moment ago:
f(x+1) - f(x) = sum_k=0^m-1 c_k+1 {x choose k}.
This is a polynomial of degree < deg f(x). So by induction, its coefficients are all integers.
So far we know that c₁, c₂, ..., c_m are integers.
But what about c₀?
Luckily, c₀ = f(0), which was assumed to be an integer. So all the coefficients are integers.

[The point of this question was to give a good way of understanding the surprising fact that a noninteger polynomial may take on only integer values. It says that the usual way of writing polynomials, as combinations of (x^k), is not good for studying this question. Rather one should work with combinations of (x choose k)s.]

Monday June 2

To any partition P of X, we associated the natural surjection X ->> P.
To any function f : X -> Y, we associated a partition of X, where the cells are the preimages of elements of image(f).

This lets us refine our previous theorem about factoring functions f : X -> Y;
any function factors uniquely as X -natural surjection->> P -> S -inclusion-> Y,
where P is a partition of X, S is a subset of Y, and P->S is 1:1 and onto;
in particular, P must be the partition associated to f, and S must be the image of f.

We defined relations, and associated to any partition of X, a relation ~_P from X to X.
Then pointed out three properties it has: reflexive, symmetric, transitive.
Any relation with those properties is an equivalence relation.
Then we looked at a bunch of relations, and figured out how they failed to be equivalence relations.

Q. Is the following an equivalence relation on N?
a ~ b iff there exists an m such that a | b^m, b | a^m.