Friday May 29

We defined a partition of a set X: it is a set P of subsets of X, with the properties that
(1) union_{S in P} S = X, i.e. x in X <=> there exists S in P with x in S
(2) for any two distinct S₁, S₂ in P, the intersection is empty
(3) the empty set is not an element of P.

We also defined the {n choose k} notation for binomial coefficients, proved the Pascal recurrence combinatorially, and proved the formula with factorials in two different ways (by induction and using a bijection).

(Note that the Wikipedia article differs from how I did things in terms of which one is the definition and which one is the theorem. I think the order given there is silly.)

Something I didn't have time to emphasize: the middle expression in

makes sense for arbitrary n, not just for integers. (k should still be an integer.) This is important for the last HW question.

Applications of number theory

I mentioned RSA encryption a number of times. What is exceptionally notable about it is that you can tell everyone "Send me messages in this secure way", and you can read the messages, but nobody else can read one another's messages. So it doesn't require you, as your first step, to smuggle a code book.

Lots more in Schroeder's Number theory in science and communication, which the library seems to have four copies of (in various editions). This is where I learned about the golden ratio's use in designing speakers.

Last HW due Friday June 6

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

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.

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

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.

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

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

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

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

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

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

Wednesday May 28

When does ab congruent to ac mod n imply b congruent to c mod n? Answer: if gcd(a,n)=1.
In general, we only learn b congruent to c mod n/gcd(a,n).

Def: the image of a function.
Theorem: every function factors as a surjection followed by an injection.
This was an existence statement; we made a uniqueness statement, which we'll prove next time.

Answers to midterm #2

Here.

Spread on midterm #2

70+ A
50-70 B
30-50 C
10-30 D
<10 F

Remember, this is only what you'd get if through some rip in the space-time continuum all other data going into your class grade were lost. Your actual letter grade will be calculated using the number, not this letter above, so don't worry about being on a cusp between two letters.

No office hours this week

I'm out of town.

Answers to HW #5

Given a natural number n and a prime p, let n_p denote the power to which p appears in the unique factorization of n. So n = product of {p^n_p : p prime}, where most of the factors are p⁰ = 1.

1. Write down necessary and sufficient conditions on the exponents {b_p, c_p} for b|c to be true.

A. For every p, b_p should be less than or equal to c_p. (I'm only writing out the English because I don't know how to produce the symbol in HTML.)

2. Give a formula for gcd(b,c)_p in terms of b_p, c_p.

A. gcd(b,c)_p = min(b_p, c_p), the minimum of the two.

3. Prove that gcd is associative, in that gcd(a,gcd(b,c)) = gcd(gcd(a,b),c).

A. Either way, the exponent on p is min(a_p, b_p, c_p).

4. Let d be a common divisor of b,c. Show that gcd(b/d, c/d) | gcd(b,c).

A. Looking at just the p-exponents, we know d_p is less than or equal to b_p, c_p. Then the statement is that for all p,
min(b_p - d_p, c_p - d_p) is less-or-equal min(b_p, c_p).
This is true; indeed, the difference is d_p.
So the better statement was
gcd(b/d, c/d) * d = gcd(b,c).

5. The continued fractions expansion of a positive irrational real number r is
r = n₁ + 1/(n₂ + 1/(n₃ + 1/...
where each n_i is a positive natural number.
OOPS possibly n₁=0, but the others are definitely positive.
If r is rational, one can do the same thing, but the expansion terminates.

a. Show that "the" continued fractions expansion exists uniquely for any rational r.
(Actually this holds for real r too, but one needs to study convergence properly to make sense of that statement, and we haven't and won't.)

First we address existence. Let r = n/d, for "numerator" and "denominator".

Proof by induction on d (which is at least 1).
If d=1, then r = n, so take n₁ = n and that's the complete expansion.
If d > 1, let n₁ be the greatest integer < r.
So r = n₁ + (n - d*n₁)/r, where the new numerator is in (0,r).
By induction, the fraction r/(n - d*n₁) has a finite continued fractions expansion.
(Here we crucially used n - d*n₁ < r to justify the invocation of induction.)
Sticking it into r = n₁ + 1 / r/(n - d*n₁), we get a c.f.exp. of r.

Now uniqueness, also done by induction on d.
If d=1, then r = n is the only c.f.exp., because having another term will spoil integrality.
Now assume d>1.
If r = n₁ + 1/(n₂ + 1/(n₃ + 1/... = m₁ + 1/(m₂ + 1/(m₃ + 1/...,
then the greatest integers less-or-equal to these three equal numbers must be the same.
For the second and third, said greatest integers are n₁, m₁.
Subtract those off, invert both sides, and you have an equality between two c.f.expansions of a rational with smaller denominator than you started (as in the previous proof).
So by the same induction, these two expansions must be equal.

b. Optional: Compute it for the square root of 5.

A. Playing around with a calculator, it is easy to see that the first few n_i are 2,4,4,4,4... which suggests that one is stuck in a loop. Proving that involves a little bit of algebra with sqrt(5).

c. Compute it for 140/49.

140/49 = 2 + 1/(42/49)

49/42 = 1 + 1/(42/7)

42/7 = 6

so 140/49 = 2 + 1/(1 + 1/6).

d. Explain the relation to the Euclidean algorithm (computing gcd(m,n) vs. expansion of m/n).

A. They're really "the same".
At each step of the Euclidean algorithm, one must compute the remainder after division of m by n. If one instead wrote down the multiple of n being subtracted,the sequence of such multiples is exactly the sequence of n_i.
The sneaky thing is that to compute the continued fractions expansion of m/n, it is not important that m,n are in lowest terms. If one never simplifies them during the computationg of the c.f.exp., the last denominator one meets is gcd(m,n). For example, gcd(140,49)=7 in the one above.

Answers to HW #4

1. We claimed several properties of gcds when stating the Euclidean algorithm. Prove them all:

a. gcd(a,b) = gcd(-a,b) = gcd(a,-b)

b. gcd(0,a) = a

c. gcd(a,b) = gcd(b,a).

A. Let's do (b) first.
Plainly a|0 and a|a, since 0 = 0*a and a = 1*a.
If b|0 (which it always does) and b|a, then b|a.
So we've checked that a is indeed a gcd of 0 and a.

Now (a) and (c). Let g be any of gcd(a,b), gcd(-a,b), gcd(b,a) (as the proofs are similar).
Then g|a and g|b. (If g|-a, then g|a, etc.)
So it is a common divisor.
Now let c be such that c|a and c|b.
Then we argue that c|g. (If g = gcd(b,a) this is easy; otherwise we use c|a <=> c|-a, etc.)
Hence g is a gcd of a and b.

2. Prove gcd is in some sense associative, in that gcd(a,gcd(b,c)) = gcd(gcd(a,b),c) for all a,b,c in Z.

A. Each one boils down to g|a, g|b, g|c, and for any h such that h|a, h|b, h|c, one has h|g.
At that point the proof becomes the same as the one showing that gcds are unique, as we did in class.

3. Prove that nⁿ > n! * 1000 (meaning n * (n-1) * ... * 3 * 2 * 1 * 1000), for all n at least 10.

A. Check the case n=10 by computer: 10! ~ 3.6 million < 10⁷, so 10! * 1000 < 10¹⁰.
Now assume n>10. We know
(n-1)^n-1 > (n-1)! * 1000 by induction.
Multiply both sides by n:
n * (n-1)^n-1 > n! * 1000
and observe that the left side is smaller than
n * n^n-1 = nⁿ.

4. For all a,b,c, show that gcd(ab,c) | gcd(a,c) gcd(b,c), and give an example where they are unequal.

A. Actually I don't know how to do this without prime factorization; with that it becomes easy.
Really I assigned it to make people appreciate prime factorization once we have it.

For an example, take a=b=c=2. Then it says 2 | 4.

Answers to HW #3

1. Let f(n) be a function from N -> N (the naturals), satisfying f(0) = 0 and for n>0, f(n) = 2 * f(n-1) + 1.
Prove that for all n in the naturals, f(n) = 2ⁿ - 1.

A. The proof is by induction on n.
The base case is n=0, which is given to us.
Now assume n>0. Then
f(n) = 2 f(n-1) + 1
= 2 (2^n-1 - 1) + 1 by induction
= 2ⁿ - 2 + 1
= 2ⁿ - 1, as we wanted to show.

2. Prove that for all n at least 2 (this induction doesn't start from 0, or from 1!),
that the product of the numbers {1 - 1/i : i = 2,...,n} is 1/n.

(I guess you can start from 1 if you want, regarding the LHS as an empty product, so = 1. But the problem doesn't ask you to think about that.)

A.
For n=2, the statement is that 1 - 1/2 = 1/2, which is true.
Now assume n>2.
Then product_i=2ⁿ (1 - 1/i) = (1 - 1/n) product_i=2^n-1 (1 - 1/i)
= (1 - 1/n) 1/(n-1) by induction
= 1/n, as was to be shown.

3. Let f:N->N satisfy
f(0) = 38
f(1) = 39
for all n at least 2, f(n) = 3f(n-1) - 2f(n-2).
Prove that for all n in N, f(n) = 2ⁿ + 37.

A. The formula is easy to check for n=0,1.
Now assume n is at least 2.
Then f(n) = 3 f(n-1) - 2 f(n-2)
= 3 (2^n-1 + 37) - 2 (2^n-2 + 37) by (strong) induction; each of n-1, n-2 are < n
= (3-1) 2^n-1 + 37
= 2ⁿ + 37 as was to be shown.

Practice midterm #2

Here.

Some links on recent material

Euclidean algorithm
GCD
Prime factorization and its existence and uniqueness
Next time:
Chinese Remainder Theorem

HW #5 due Friday May 16 (problem 5 edited)

Given a natural number n and a prime p, let n_p denote the power to which p appears in the unique factorization of n. So n = product of {p^n_p : p prime}, where most of the factors are p⁰ = 1.

1. Write down necessary and sufficient conditions on the exponents {b_p, c_p} for b|c to be true.

2. Give a formula for gcd(b,c)_p in terms of b_p, c_p.

3. Prove that gcd is associative, in that gcd(a,gcd(b,c)) = gcd(gcd(a,b),c).

4. Let d be a common divisor of b,c. Show that gcd(b/d, c/d) | gcd(b,c).

5. The continued fractions expansion of a positive irrational real number r is
r = n₁ + 1/(n₂ + 1/(n₃ + 1/...
where each n_i is a positive natural number.
If r is rational, one can do the same thing, but the expansion terminates.

a. Show that "the" continued fractions expansion exists uniquely for any rational r.
(Actually this holds for real r too, but one needs to study convergence properly to make sense of that statement, and we haven't and won't.)

b. Optional: Compute it for the square root of 5.

c. Compute it for 140/49.

d. Explain the relation to the Euclidean algorithm (computing gcd(m,n) vs. expansion of m/n).

Wednesday & Friday May 7 & 9

Wednesday:
Subrings of the complex numbers.
Irreducible vs. prime.
In {a + b sqrt(-5)}, 2 is irreducible but not prime.
Prime => irreducible.

Friday:
In Z, irreducible => prime.
Unique factorization.
We did unique factorization by weak induction on the number of primes being multiplied together; maybe it would have been more intuitive to do it by strong induction on n. (We found two factorizations of n/p_k, and could have said "since n/p_k < n, by induction we know that...")

Monday May 5

We proved that the Euclidean algorithm does, indeed, calculate gcd(a,b).
I mentioned a couple of fun properties of it, like the relation to Khinchin's constant.

Then we proved what will be a much more useful result:
for any a,b in Z, there exist x,y in Z such that gcd(a,b) = xa+yb.

HW #4 due Friday May 9 (back on schedule)

In the below you're only allowed to discuss gcd using the definition from class, not stuff you might know about it related to e.g. prime factorization. We haven't proven that yet.

1. We claimed several properties of gcds when stating the Euclidean algorithm. Prove them all:

a. gcd(a,b) = gcd(-a,b) = gcd(a,-b)

b. gcd(0,a) = a

c. gcd(a,b) = gcd(b,a).

2. Prove gcd is in some sense associative, in that gcd(a,gcd(b,c)) = gcd(gcd(a,b),c) for all a,b,c in Z.

3. Prove that nⁿ > n! * 1000 (meaning n * (n-1) * ... * 3 * 2 * 1 * 1000), for all n at least 10.

4. For all a,b,c, show that gcd(ab,c) | gcd(a,c) gcd(b,c), and give an example where they are unequal.

Answers to HW #2

Let f:X->Y and g:Y->Z be functions.

1. Give an example where g o f is onto, but f is not onto.

Let X = {a}, Y = {3,green}. Let f = {(a,green)}, and g = {(3,a),(green,a)} (the only possibility for g).

2. Assume g o f is 1:1, and f is onto. Show that g is 1:1.

Let y1,y2 in Y have g(y1)=g(y2). We want to show y1=y2.
Since f is onto, there exist x1,x2 such that f(x1)=y1, f(x2)=y2.
So (g o f)(x1) = g(f(x1)) = g(y1) = g(y2) = g(f(x2)) = (g o f)(x2).
Since g o f is 1:1, x1 = x2.
Hence f(x1) = f(x2), i.e. y1=y2.
So g is 1:1.

3. Let X have 2 elements and Y have n elements. Show, by induction on n, that the number of 1:1 functions from X to Y is n²-n.

[Actually it was silly to do this by induction, I realized later -- one can count all function, n², and subtract the noninjective ones, in which both elements of X go the same place. There are obviously n of those, depending on the choice of place.]

If Y is empty, there are no functions, and 0 = 0² - 0.
Otherwise, we may pick an element y in Y.
The functions f from X to Y that don't hit y (i.e. such that there doesn't exist any x s.t. f(x)=y) are exactly the same as the functions from X to Y \ {y}.
By induction, the number of those is (n-1)² - (n-1) = n² - n - 2(n-1).
So how many more 1:1 functions are there from X to Y, that do hit y?
Call the elements of X be {a,b}.
Then either f(a) = y, and f(b) is not y (since f is 1:1); there are n-1 choices for f(b).
Or f(a) is not y, in which case f(b) must be y (since f hits y); there are n-1 choices for f(a).
So there are 2(n-1) more functions,
for a total of (n² - n - 2(n-1)) + 2(n-1) = n² - n.

4. Assume that X=Z, so g:Y->X.
The function I:X->X such that I(x)=x for all x in X is called the identity function.
(Every set's got one!)
Call g a left inverse of f if g o f is the identity function on X.

a. If g is a left inverse of f, show that f is 1:1.

Let x1,x2 be in X, and assume f(x1)=f(x2). Apply g to both sides. Then x1 = I(x1) = (g o f)(x1) = (g o f)(x2) = I(x2) = x2.

b. If f is 1:1 and X is nonempty, show that f has a left inverse.

Since X is nonempty, we may pick some element x₀ in X.
Define g:Y->X as follows.
For each y in Y such that there exists an x in X with f(x)=y, let g(y)=x.
For the remaining y in Y, let g(y) = x₀.

First we have to argue that this g really is a function, i.e. that it assigns a unique value to every y. Certainly it assigns a value, since we caught any stragglers with "for the remaining y...". If in the first line, g(y) was pointed toward x1 and x2, then f(x1)=y=f(x2). But since f is 1:1, this forces x1=x2.

Second, we have to show that this g is a left inverse.
For all x in X, g(f(x)) = x by the first line of the definition of g.

[One could also define g as a set of ordered pairs; it is the union of {(y,x) : (x,y) in f} and {(y,x₀) : there doesn't exist x in X with f(x)=y}. Then one again has to use injectivity of f to show that this is indeed a function.]

c. If X is empty, show that f is 1:1, and determine when it has a left inverse.

One definition of f 1:1 started with "given two elements x1,x2 of X, unequal, ..." but there are no two such elements. So the condition is vacuously true.

For g to be a function from Y to an empty set X, Y has to itself be empty. In this case f has a left inverse: the empty function.

Friday May 2

We talked about induction, and proved by induction that n² = 2n² for all naturals n. (Proof: n=0 is easy. Then for n>0, use the equation at step n to get the one at step n+1. No division by zero occurs.)

I talked about a curious induction proof in which the base case is at n=5. The cubic equation is solvable, and was solved by Tartaglia, but equations of degree 5 and higher are not.

Then we showed that gcds are unique. The case of gcd(a,b)=0 had to be made separately.

I stated the Euclidean algorithm to compute gcds, but didn't show that it terminates nor that it, in fact, computes gcds.

Wednesday April 2

First we proved that there are no natural numbers between 0 and 1, hence only one integer strictly between -1 and 1.
This is handy later; it says that the only multiple of d strictly between -d and d is 0.
Then we proved the "division algorithm":
given an integer n and a natural d>0, there exist unique integers p,r with r in [0,d) such that n=pd+r.
Then we introduced the "divides" notation a|b, and proved a couple of easy things about it. More to come.

Second midterm Friday May 23

The second midterm will be on Friday May 23.