My office hours are MTWF 12:15 to 1:15 and by appointment. I'm also usually around in the late afternoon and early evening, except Wed. and Thurs. but often including weekends. For tomorrow, I'll be here in the evening from around 7:30 or 7:45 until 9 or 9:30, and on Thurs. I'll be here in the afternoon from 2 to 5:00. Also, on Friday evening (I think) and/or Sat. and Sun. afternoon/early evening. I will make additional copies of the material if you missed anything.
For a nice collection of quote on prime numbers, see M. Watkins' web site (thanks to Michael Somos for the pointer).
For information on course mechanics, be sure to check the grading scheme and exam schedule page.
Review session tomorrow night Tues. 9pm Reiss 281 where we will go over assignments for class participation on Wed., Friday and Mon. Those who are late in returning will still get their chance ;-) See below for more info on these final days of class - which replace the need to prepare for a class final!
Please read for overview the two chapters I mentioned: Chaps 9 and 10, which will occupy us for Mon. and Wed.
Monday, I gave back the exams and talked about the Legendre and Jacobi symbols. There was a simple quiz on the latter (with formulae on the board). As an additional exercise, I asked you to do 9-3 #2. I suggested that it will probably use one of the theorems of that section - and a moment's looking will suffice to find one of almost the same form (except for odd primes rather than general odd positive integers). However, the mechanics may not be obvious to go from the theorem to the exercise, which is really just a corollary. The way to handle such things is to first try a simple example, say with two smallish odd primes. With a bit of experimenting you can see why it works for odd numbers which are the product of two primes. I'll be content with that; the case for any product of primes can, I guess, be derived by induction ... But even for two primes, you need to be just a bit brave. The result is true so, as you'll see, a rather unlikely looking claim of divisibility must be true - and then once you see from simple examples what is happening, you can verify it. At least show me that you are trying these even if you don't completely figure it out.
Last three classes to involve student participation I estimate that each of you will need to spend at least 4 hours to do a credible job. At least two of those hours must be spent working with me, probably with a few of your friends. To facilitate this, I'll be around for extra hours, including this break. Look for me in the evenings and late afternoons. I'm here now (Monday evening and room 256 is open - see below).
So what topics will we split into groups to study and present? And what sort of materials should you prepare for the presentation? Copies of the relevant material is in the math dept lounge (Reiss 256) so you can come by at your leisure and pick up the packets related to your topic below. Thanks to Caroline for her suggestion.
On Wed., the 16th we split into three groups. I also announced a special session Tues. night April 22 (after the break) at 9pm, where I'll go over the material with you and we can plan the presentations and work. Of course, for Wed. that doesn't leave a lot of time (but that's what nights are for ... and you'll be done early with your presentation). Remember, though, that you are responsible for the other work, too, though not to the same degree of depth as with your own topic. These extra presentations give me a good chance to find ways to give you the benefit of the doubt (in cases where your test and quiz scores aren't great and especially if you've been lax on homework). The presentations also give you a chance to learn some neat stuff!
The topics I discussed in class are:
Since there will be 8 or 9 in each group, no one person will be responsible for all of it - but you'll have to work hard to get enough of the gist so that you can contribute your part. Dividing 50 minutes and allowing for intro and summary, you'll only have to talk for 4 or 5 minutes, if we all speak. However, I want you to also write up a summary so this means that probably a division of labor (speakers and writers) will be more efficient. How much to write? Just enough so that your classmates can get the key idea or two - which will be the content of the take-home. I'll require each person to answer something about his or her own group topic, and also something (less detailed) about one of the other two topics.
I did mention that you could try something different from the above if there is some topic that really interests you, but talk to me first. I mentioned one area in particular involving representation of number-theoretic facts using graphs. For instance, it is not hard to show that if one lists the numbers 2,3, ..., p-2 from left to right along the x-axis (p odd prime at least 5) and if one connects i to j by an arc in the upper half-plane whenever i*j is congruent to 1 (mod p), then the resulting arcs determine a graph which is regular of degree 1 - i.e., each vertex i in {2,...,p-2} is adjacent to a unique j (not equal to i), as we used in the second proof of Wilson's theorem given in class - and some pair of arcs will cross when p is at least 7. THat is, the only odd primes for which the resulting graphs are crossing free are p = 3 and 5.
I'm not going to type up all of the material or even comment on it here - however,
some occasional remarks may appear ... For instance, regarding primes, the second
page of the section on Primes (copied from Ch. 12 of Hardy and Wright) asserts
that for complex numbers z we have an equation
(1) z^2 - 2Re(z)z + |z|^2 = 0,
where z = a + bi, i^2 = -1, real part of z = Re(z) = a, and
norm of z = N(z) = |z|^2 = a^2 + b^2, as usual.
How does one get such an equation?
Let z-bar (z with a "bar" over it) denote the complex conjugate of z, z-bar = a - bi. Then
0 = z^2 - z^2 - z*z-bar + z*z-bar = z^2 - z(z + z-bar) + z*z-bar = z^2 - (2Re(z))* z + |z|^2,
since z plus its conjugate is twice the real part while z times its conjugate is a^2 + b^2.
In fact, this argument is purely "formal" and works whenever one has the notion of conjugate,
real part and norm as we will see again for the quaternions.
For the case k(rho), written here as k(r), (also known as the "Eisenstein integers"),
the notion of conjugate is a bit different. One defines r as the cube root of unity;
i.e., r = e^(2pi*i/3) so r^3 = e^(2pi*i) = e^0 = 1. Using de Moivre's formula, which
states that e^(iy) = cos(y) + i sin(y) with cos(2pi/3)=-1/2 and sin(2pi/3)=sqrt(3)/2,
we get e^(2pi*i/3) = (1/2)(-1 + i*sqrt(3)). Hence, r^2 = r-bar = (1/2)(-1 - i*sqrt(3)),
so r + r^2 = -1, or 1 + r + r^2 = 0. Conversely, if you use the quadratic formula,
the latter equation has roots [-1 +/-sqrt(-3)]/2, which are r and r^2, respectively.
Let alpha = a + br be any Eisenstein integer. Then
r + r-bar = a + br + a + br^2 = 2a + b(r + r^2) = 2a - b, and
N(r) = r * r-bar = a + ab(r + r^2) + b^2 = a^2 -ab + b^2 = (a - b/2)^2 + (3/4)b^2,
which is nonnegative (and zero if and only if a = 0 = b, i.e., if and only if r = 0).
Now we get the same equation as above
(2) r^2 - 2Re(r)r + N(r) = 0.
Both of these equations (1) and (2) being satisfied by Gaussian and Eisenstein integers,
resp., have a and b ordinary or "rational" integers so the Gaussian and Eisenstein
integers are quadratic integers as defined in H & W, that is, they satisfy quadratic
equations with integer coefficients. (Note that for both types, the second coefficient
would be integral even if Re(r) were a half-integer, but that wouldn't work for N(r).
Later, for the quaternions, this turns out to not be a problem and so we can already
see why half-integers may play a special role.)
The take-home will be given out on the last day of class, Monday the 28th, and will be due by Friday, May 2.
Mon. March 31: 6.2#2 and 6.4#11 - I don't have all the homework yet so I hope that you will turn it in soon (i.e., by Wed.) if you want to get credit. Also on Wed. April 2, please do 7.2#2. (We did 6.1 #4 in class so if you weren't there, try the problem on your own.)
I gave two proofs in class that a^2 congr to 1 (mod 8) when a is odd: First proof: 1,3,5,7 squared are all congruent to 1 (mod 8). Since any other odd number is congruent to 1,3,5,7 (mod 8) and since a^2 is congr to b^2 whenever a is congr to b, this sufficies. Second proof: if a = 2k+1, then a^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1. But for all k, k(k+1) is divisible by 2 so 4k(k+1) + 1 congr 1 (mod 8).
For Friday April 4, find the analogous theorem to Thm 8-5, but replacing "2" by "n". (You don't need to write it up.) Also, check one of the steps of 7-2 #2 which we mentioned in class: if s congruent to 1 (mod 2^n), then s^2 congruent to 1 (mod 2^{n+1}). One more thing for Friday, look ahead at the proof of Thm 8-8 up through 8-2-4 and read the first two sections of Ch. 9. The midterm on Tues. 8 April will stop with Chapter 9 - and I will probably make it an "open book" midterm (so don't worry about memorizing things - but you do need to know what they mean and how to use them, both of which abilities tend to come from doing the homework!
We discussed Chap. 8 and I pointed out that there are some very nice proofs, and that these proofs often have some slightly hidden subtle points which are best discovered by trying to actually carry out the steps sketched in the proof - i.e., by filling in any ``gaps'' in the argument. Also, some of the theorems are used later to prove others - not necessarily immediately following. For instance, Thm 8.2 is used in the proof of Thm 8.4. Using some analysis (given in Appendix B), Thm 8.3 implies that the series sum (1/p) p prime, does not converge - so the primes are not too sparse. In the proof of 8.3, the set Lambda is an infinite set - e.g., if M=6, Lambda consists of all integers which have no prime factor bigger than 6 so Lambda is all integers of the form 2^a x 3^b x 5^c, a,b,c nonnegative integ. But the proof claims that sum_(n in Lambda) 1/n is a finite product of finite sums, hence a finite number. This is true but can you see why? In the proof of Thm 8.4, the line immediately above 8-1-1 has an inequality. Why is it true? The rest of the proof is a tasty example of analysis - a quintessential epsilon-delta argument. The result of Thm 8.4 says that the primes are also not too dense. Thm 8.5 has a simple proof which you should study - I recommend checking that the last line on the page actually holds by doing the algebra.
We went over B1 thru B4 from the handout on the "bracket" function, and I left some details up to you for checking ;-) There are some exercises below as part of the presentation on bracket functions. Here is one to try for Friday; it just uses the theorems below.
Find E(5,216) and E(11,216); see below for the definition of E(p,n). We did one like this in class on Friday so it would be fair game for a quiz on Monday. At this point, you should be able to do any of the exercises on the midterm key (see below).
The following notes relate to the ``bracket function'' in your handout.
This is the function defined for any real number x by [x] = n
if n is the greatest integer less than or equal to x.
The reader should note that if n and m are positive integers, then [n/m]
is the number of positive integers less than or equal to n and divisible by m;
indeed, these are exactly the numbers m,2m,...,[n/m]m;
when n < m, the set is empty.
On the handout the following are shown:
B1: If m is an integer and x is any real number, then [x + m] = [x] + m.
B2: There is a functional identity 1 + [x] + [-x] = chi_Z(x), where chi_Z(x) = 1
if x is an integer and 0 if x is not an integer. (The term ``functional identity''
means that the equation holds for every real number x.)
B3: For all real numbers x and y, [x] + [y] <= [x + y] <= [x] + [y] + 1.
B4: If n is a positive integer and x is a real number, then [[x]/n] = [x/n].
We'll use the last one below.
Let E(p,n) denote the power to which the prime p occurs in the prime factorization
of n! - so, e.g., E(2,4) = 3, E(3,4) = 1, and E(5,4) = 0 since 4! = 2^3 x 3.
Can you show that, for p prime, p divides n! if and only if p is at most n?
I sketched a proof of the following in Friday's class (March 7):
Theorem 1. For every prime p and positive integer n,
E(p,n) = [n/p] + [n/p^2] + [n/p^3] + ...
The sum has finitely many nonzero terms since eventually p^k exceeds n.
Proof. By the note above, the k-th term counts the number of factors of n! which
are divisible by p^k. Hence, each time p appears in the prime factorization of n!
one and only one of these terms will contribute 1 to the sum, and this suffices.
Exercise [1]: Give the details.
Theorem 2. For every prime p and positive integer n,
E(p,n) = n_1 + n_2 + n_3 + ...,
where n_1 = [n/p] and n_(k+1) = [n_k/p], for k a positive integer.
Proof. This is an application of B4 (Exercise [2]).
Theorem 3. Suppose n = a_0 + a_1 * p + a_2 * p^2 + ... + a_k * p^k, where
k, n and a_0, ... ,a_k are positive integers (a_k nonzero); that is, suppose
that the base-p representation of n is (n)_p = (a_k, ... ,a_0). Then for any
prime p,
n - (a_0 + a_1 + ... + a_k)
E(p,n) = -----------------------------
p - 1
This formula is due to Legendre.
Proof. Here are some hints for a proof using Thm 2. Since n = sum_(j=0 to k) a_j p^j,
n_1 = [n/p] = sum_(j=1 to k) a_j p^(j-1)
n_2 = [n_1/p] = sum_(j=2 to k) a_j p^(j-2)
...
n_(k-1) = sum_(j=k-1 to k) a_j p^(j-k+1) = a_(k-1) + a_k p
n_k = sum_(j=k) a_j p^(j-k) = a_k.
Hence, n = n_1 p + a_0
n_1 = n_2 p + a_1
...
n_(k-1) = n_k p + a_(k-1)
n_k = a_k
Now finish the argument.
-------------------------
To see how these three theorems work, consider E(3,101), that is, the exponent
of 3 in the prime factorization of 101! - a bit too large for handcalculators
and even for most computational programs. But we can get it easily:
Using Thm 1, E(3,101) = [101/3] + [101/9] + [101/27] + [101/81] = 33 + 11 + 3 + 1,
so E(3,101) = 48. By Thm 2, we have [101/3] + [33/3] + [11/3] + [3/3] = 48,
while by Thm 3, E(3,101) = (101 - (2 + 0 + 2 + 0 + 1))/2 = 96/2 = 48.
Here is a "key" with hints for our midterm which involved Primitive Pythagorean Triples.
We define (a,b,c) to be a PPT if a,b,c are positive integers, and
a^2 + b^2 = c^2 (1)
and
gcd(a,b,c) = 1 (2)
#1 Hence, (a,b)=(b,c)=(a,c)=1 (3)
Pf. By (1) each of a^2,b^2,c^2 is an integer linear combination of
the other two. Hence, if a prime p divides two of them, it also
divides the third. But for any integer n, p | n iff p | n^2.
#2 Exactly one of a and b is odd - WLOG a is odd and b is even.
Pf: By (3) it suffices to show that not both a and b are odd.
Since n^2 is congruent to 1 if n is odd and to 0 if n is even (mod 4),
a and b odd implies that a^2 + b^2 is congruent to 2 (mod 4). But c^2
is not congruent to 2 since c is an integer by assumption.
#3 Show that there exist pos. int. r,s such that a = r^2 - s^2 and b = 2rs.
Pf. By (1) and result #2, c^2 is odd so c is odd. Hence,
Here's the key hint (Spoiler) Using the hint, the remaining exercises are not much harder than #1 and #2 above. But the results are so pretty that I hope you will appreciate their elegance. BTW, all of these amazing consequences of being a PPT show why Fermat's conjecture (aka his ``last theorem'' - recently proved by Wiles) is so plausible. That is, if the many consequences weren't mutually consistent, then no triple would satisfy them. Hence, one can at least appreciate why it is unlikely that integer solutions should exist for x^n + y^n = z^n when n is an integer bigger than 2.
there exist u and v positive integers such that c + a = 2u and c - a = 2v. Hence, b^2 = (c + a)(c - a) = 4uv, and since b is even, b = 2w, so w^2 = uv. Exercise alpha: (u,v)=1; Exercise beta: there exist r and s positive integers with u = r^2 and v = s^2 (hint: use exercise alpha to establish beta). Hence, by beta, w = rs, so b = 2w =2rs, and 2a = (c + a) - (c - a) = 2(u - v). Thus, a = u - v = r^2 - s^2. This establishes #3. #4 Deduce any other properties of PPTs. First, let's see that #3 can be extended to give a complete description of all PPTs. We've shown that if (a,b,c) is a PPT (i.e., satisfies (1) and (2)), then exactly one of a and b is odd, say a, and there exist r,s pos. integ. such that a = r^2 - s^2, b = 2rs (4) In fact, the conditions on a and b force r,s to satisfy r > s, (r,s) = 1, and r not congruent to s (mod 2) (5) The first claim follows from a > 0, the second is Exercise gamma, and the third is Exercise delta. To show that r and s have different parities, it suffices to show that they both can't be even - but this follows from our assumption on a. Now we will show that given any two positive integers r and s which satisfy (5), if we define a and b using (4), and set c = r^2 + s^2, then (a,b,c) satisfies (1) and (2), and a is odd. Indeed, exactly one of r and s is odd so a must be odd. The Pythagorean equality (1) is a trivial algebraic identity in r and s, so it suffices to show (2). Suppose p is some prime which divides each of a,b,c. Then p is at least 3 since a is odd. Also, p divides a + c = 2r^2 so p | r. Similarly, (Exercise epsilon) show that p divides s. But (r,s) = 1. Here are some additional properties of PPTs (a,b,c) which satisfy (4) and have a odd. Exercise zeta: 4 | b; Exercise eta: 3 divides a or 3 divides b (but not both - i.e., it is the exclusive ``or'' here) (Hint: the approach is somewhat like that in #2). Exercise theta: 5 divides one (and hence, exactly one) of a,b,c. If we call a and b the ``legs'' of the triple, and c the hypoteneus, while ``side'' means leg or hypoteneuse, then the preceding can be stated: in a PPT, at least one leg is divisible by 4, one leg is divisible by 3, and the product of the two legs is divisible by 12. Also, exactly one side is divisible by 5 and the product of all three sides is divisible by 60.
For the midterm, we'll cover 4.1,4.2,5.1,5.2,5.3,6.1, and suitable earlier stuff. For review for Monday's class, do 6.1: #8,12,13 (these are actually done in the back of the book but try them without looking!) Then try 9 and 10 of the same section, which use the result from #8.
For Monday 2-24 , read through section 5.3 (the Chinese Remainder Theorem) and do the following problems: 4.1 #2(a,b),5,7(a,d); 5.1 #1,2(a,c,e),3; 5.2 #2,4,6,11. I won't ask you to write them up but do be ready to put them up at the board.
For Wed., I gave a problem in class which is too long to write down again here. Please see a classmate to get the problem if you weren't there. I have copies of Chapter 5 if you don't yet have the book, and I'll leave some in the math dept lounge in Reiss 256. Also, try the other problems that we didn't yet review in class.
Meanwhile, for Wed. 2-12, to be collected please do the following two exercises. Recall that a number n is called perfect if the sum of its divisors (including 1 and n) is twice n. E.g., 12 = 1+2+3+6, so 6 is perfect.
1. Show that if (2^k)-1 is a prime, then
k-1 k
n = 2 * (2 - 1) is a perfect number;
for instance, 6 = 2 * 3 and 28 = 4 * 7 are perfect numbers.
2. Show that if (2^k)-1 is prime, then so is k. (Hint: Remember
theorem 1.2 in the book.)
For Friday the 14th, section 4.1, please do 2a,b and 5, and read also 4.2.
Please look over the 1st section 3.1 of Chapter 3 and do 3.1: 1,3,8,10 for homework Also, look at the results from 3.2 and do problems 3.2: 3,5,6. Homework was discussed on Monday but if there were any of them that weren't clear, ask! (Try discussing them among yourselves first though.)
practice problems for a quiz ...? ;-)
1. If gcd(a,b)=1 and gcd(b,c)=1, with 1 < a < b < c, how large and how small can gcd(a,c) be? 2. Show that lcm(ra,rb) = r*lcm(a,b) for a,b,r positive integers. 3. Show that lcm(ra,rb) = |r|*lcm(a,b) for a,b,r nonzero integers (Hint: use #2 and a bit of algebra.) |r| means absolute value of r as usual. 4. Give a combinatorial proof that the alternating sum of the binomial coefficients C(n,0), ... ,C(n,k) is zero (alternating means to put alternatingly plus and minus signs in front of the terms just as in elementary calculus). Hint: Show this holds when n is odd by using problem 3.1 #8 and then take care of the n even case by using 3.1 #3. 5. Consider the sequence a_n = 2,7,9,16,25,41,66,... (i.e., with a_1=2, a_2=7, and, recursively, a_n = a_(n-1) + a_(n-2) for n at least 3). Prove that a_(n-2) + a_(n+2) = 3*a_n for n at least 3. 6. Show that this same property holds no matter what a_1 and a_2 are; that is, it only requires the recursion. (This second proof makes use of the "self-similar" nature of Fibonacci-type sequences; they are actually one-dimensional fractals ;-) 7. Use the theorem on Diophantine equations to show that 15x + 17y = 143 has a unique solution if both x and y positive must be positive. 8. (extra) What are the three "stellated polygons" (see 3.3) on 7 points?
For Wed. 29th Jan., please do 2.2: #1b,5b,10; 2.3: #2,7; 2.4: #8,9b. The problems will be collected. Note that I made the assignment shorter by leaving out numbers 4,5 and 7 from 2.4 (though you should try them anyway ;-)
Sean asked about the meaning of integral multiple, which doesn't seem to be defined in our text. (Can anyone find it given there?) Here is my definition:
An integral multiple of x means nx, where n is an integer. So if a and b are nonzero integers, a divides b if and only if b is an integral multiple of a. The text _should_ define it, but I also didn't find anything explicitly written. However, the term does mean just what one would think it should mean. But there is a bit of ambiguity about whether or not zero is included. Of course, zero is zero times anything else, so in that sense, zero is an integral multiple of anything. On the other hand, if a and b are nonzero, then a divides b if and only if b is a nonzero integral multiple of a.
Carl asked about the meaning of "perpendicular distance" in 2.3 #7. The distance from the origin to the line y = x-1 with slope 1 and y-intercept -1 is not 1 which is the absolute value of the y-intercept; rather, it is sqrt(2)/2 - i.e., the length of a line segment from 0 perpendicular to the line y=x-1. The word "perpendicular" is redundant for distance from a point to a line if you are in a Euclidean space (or even in Hilbert space ;-) You will want to use the following fact about perpendicular lines: the product of their slopes is -1 (unless one or the other is vertical).
The last sections on Chapter 2 are now xeroxed and in the math dept lounge. I've also made copies of Chapter 3, but I hope that all of you will soon have the text. By the midterm on Wed. Feb. 5, we will cover Chapter 3, sections 1-3, with the emphasis on sections 2 and 3.
For Jan. 24, try the following nice application of the theorems from class today. Show that if n,k,m are positive integers, then n(n+1) = k^m implies that m=1 - that is, the product of two consecutive nonzero integers can never be a nontrivial power. Don't forget that there might be a quiz!
For Jan. 22, homework was to read the rest of Chapter 2 and (not for collection) do the two exercises which follow. Recall that for integers a and b, a divides b if there is an integer q with b = aq. For a,b integers, gcd(a,b) = d if (i) d > 0, (ii) d divides a and d divides b, and (iii) if f divides a and f divides b, then f divides d.
(1) Show that for integers a and b, if a divides b and b divides a, then either a = b or a = -b. (2) Show that the gcd of two integers (at least one of which is nonzero) is unique provided that it exists. In fact, we will prove that gcd's do exist but exercise (2) is to show that uniqueness follows easily from exercise (1). *** here's the proof of (2): if d and d' are both greatest common divisors of a and b, then each is a common divisor so d|d' and d'|d. By (1) d = d' or d=-d'. But both d and d' are positive by definition of gcd, so d=d'.
For Friday, Jan. 17, please do the following problems: 1.1 #8,14; 1.2: #4 and also find a set of 6 integers which suffice to determine the weight of any integer between 1 and 87 (an extension of #3). Also for 1.2, find an integer value of k (at least 4) so that, converting the expansion of pi with respect to k, we find a perfect square in one of the truncations. Also for Friday, 2.1: #4,5,7.
Please write these problems up for collection! Quiz-wise, could you prove that n < k^n for n,k pos. int. with k > 1? Could you prove that the basis representation theorem implies the Euclid division lemma?
The last problem in section 1.2 was described more fully in class. To remind you, pi has the base-10 expansion 3.14159265..., so its truncations are 3, 31, 314, 3141, 31415, and so on. Haken has conjectured that no such base-10 truncation of pi is a perfect square ;-). Base-5, the expansion of pi would be 3.03... since pi is bigger than 3 and pi - 3 is less than 1/5, more than 3/25 but less than 4/25, and so forth. The corresponding base-5 truncations of pi are 3, 30, 303 which, as positive integers, are 3, 15, 78, also not perfect squares. But there _is_ a choice of base k for which the second truncation is already a perfect square. BTW, if we replace pi by another transcendental number e (base of the natural logarithms) and the condition of perfect square by perfect cube, then Haken's conjecture would already be false even base-10.
Back to the classroom page .
pck