The Final is Tu 12/13, 8-11 am, in our usual classroom. It will be comprehensive for the material covered on the hour exams. (That is, nothing on rational approximation.) There will be 4 20 pt problems and a choice of 15 pt problems, from which you should pick 8.
Sa 12/10 -- I was in my office from 2-3 for Reading Day. Two people picked up exam 2; one asked questions.
F 12/9 -- Test 2 returned. A majority of the class had | T1 - T2 | equal to 0 or 1. Amazing.
W 12/7 -- Brief discussion of test 2; more on the approximations to the square root of 2, with references to continued fractions and linear recurrences and the equation | x^2 - 2y^2 | = 1. Not on final.
Test 2 will be Tuesday night, December 6, 7-9pm, in 141 Altgeld.
A student writes: "Was homework #7 problem 8 just overlap material
from test 1, or is it a subject for test 2?
My reply: "Any equation of the form x^n = a mod p would
be approached via primitive roots, not lifting. Of course, it's a
candidate topic for the final."
M 12/5 -- Review for test 2. The topics discussed were mainly about primitive roots and their use in solving the equation x^n = a mod p. There was some discussion of Diophantine equations. There will be no problem on test 2 that can only be solved by the "point-slope" method. The Final will have a part in which you may choose problems from a larger set, and a point-slope problem might appear there. The ICES forms will be distributed on W 12/7 or F 12/9.
F 12/2 -- HW 10 returned and discussed. More on rational approximation; mostly material from 6.1 and 6.2. This will not be on the exam.
W 11/30 -- HW 10 collected and discussed to some extent. A bit more on quadratic reciprocity, and then the final (untested) topic: Farey sequences and rational approximations.
M 11/28 -- Endgame. The second test will be Tuesday night, December 6 at 7 pm, in a room to be announced. I reported 3 errors in HW 10: namely #7: (x,y) -> (y,z); #9: it's really an example, not a counterexample; #13: there are parentheses missing from a over p. I finished the proof of quadratic reciprocity. Starting W 11/30, I'll be reviewing material at a higher priority than introducing new stuff, but the new stuff will be from 6.1 at first.
F 11/18 -- A gratifyingly high turnout on the day before vacation, but I'd already promised not to do anything that would be specifically needed on a test. After returning HW9, and giving a handout that summarized 11/16's work, I proved, essentially, Theorem 3.9 and Theorem 5.10. Coming up in the last two weeks: the full proof of quadratic reciprocity, answering questions, preparation for test 2 (to be scheduled!) and finishing the course. Bring questions!
W 11/16 -- I got surprisingly far in the proof of quadratic reciprocity; through the proof of Gauss' Lemma (Thm. 3.2), and a direct proof of the value of (2/p). The proof was worked out simultaneously with the specific example of (a = 5, p = 13).
M 11/14 -- A bit more on HW8, a bit more on the point-slope method. Introduction to quadratic reciprocity. First the theorem and the applications, and later, the proof. There is but one more HW assignment, the Tenth Homework . This is due the Wednesday after Thanksgiving. It contains two more problems than the usual hw, and the highest possible grades are 9/7 for undergrads and 12/10 for grads. One last chance to catch up.
Regarding HW9, a student writes: "On question 4, the book uses
the function omega(n). What does that function tell us?
F 11/11 -- Most of the class period spent going over HW 8, with a bit
more on the point-slope method at the end. We'll finish up on that
on Monday, and start on quadratic reciprocity.
My reply: Sorry. I didn't use it in class, but omega(n) (see p. 188)
is the number
of distinct prime factors of n.
"Also, can you give any hints to help with question 5?"
My reply: In question 5, you should look at the possible values for
the squares mod
3 and the squares mod 5.
W 11/9 -- Error in problem 9b -- write 2004 for 2006! Handout from the web on odd perfect numbers. More on pythagorean triples, and, in fact, on solutions to the equation x^2 + y^2 = k z^2 in integers, for k = 1, 2, 3. At the end, a discussion of the point-slope method, which will get more detail on Friday.
M 11/7 -- The characterization of even perfect numbers. The complete story regarding solutions to the equation ax + by = c in integers. A start on Pythagorean triples; that is, solutions to the equation x^2 + y^2 = z^2 in integers. More on W. The Ninth Homework was distributed.
Some homework questions and answers or hints:
Q: #4: Concerning the hint, does e = phi(p)
A: Not necessarily. You're told that g is one primitive root, and so g' is
not only a primitive root, it also can be expressed as g^e for some
exponent e. For example, 2 and 8 are both primitive roots mod 11 and 8 =
2^3.
Q: #5: Is there any other hint you can give about this problem?
A: Look at the proof of theorem 2.39
Q: #7: Is there no such a?
A: For every prime p, a=0 and a=1 give solutions.
There are others.
Q: #8: I understand what you said in class about this problem,
but still am confused. Any hints as to "Your criterion on j
will depend on p (mod 8)"?
A: Look at p = 1 mod 8, p = 3 mod 8, p = 5 mod 8, p = 7 mod 8
F 11/4 -- Yet more on multiplicative functions, including when tau(n) and sigma(n) are integers. Completion of proof of the Mobius inversion formula and hints on HW 8. In particular, sigma(p^j) = 1 + p + p^2 + ... + p^j, and the question is: when is this summation = 0 mod 8?
W 11/2 -- More on multiplicative functions, especially the mysterious Mobius mu-function, which has odd connections with the Euler phi function. The (optional) handout was a printout of a webpage devoted to multiply perfect numbers; that is numbers n so that sigma(n)/n is an integer. Here is a link: Multiply perfect numbers. This was the first page that google gave me; there might well be other and better ones. If you find one, let me know.
M 10/31 -- HW 7 was returned. We change topic drastically to that of arithmetic functions. (Note, that's an adjective, with a stress on "met".) I use a different notation from the book, with tau(n) instead of d(n) to denote the number of divisors of n. We had a bunch of numerical examples. We proved Thm. 4.4. The Eighth Homework was distributed and is due on M 11/6. The second test won't happen until after Thanksgiving.
F 10/28 -- HW 7 collected, HW 8 will be out on Monday. Some of the homework problems were discussed and then I finished off primitive roots. Some material was stated, with details in the book.
W 10/26 -- There exist primitive roots mod p. A table of a^n mod 13 was distributed as an illlustration of the theorem (2.37) about the solutions to x^n = a mod p. A few side-remarks about HW 7, but no big "hints".
M 10/24 -- Tests back. Ex. 11, 12 from p. 88 done by request, and a review of a fumbled theorem from the end of F 10/21; namely, if q is a prime and q^j divides p-1, then there are q^j - q^{j-1} numbers a mod p whose order is exactly q^j. Worked out in excruciating detail mod 13.
F 10/21 -- Tests will be back Monday. Handout on the order of integers mod m, for m up to 12. Much on polynomials with integer coefficients, viewed mod m and especially mod p. Bounds on the number of solutions based on the degree. The Seventh Homework was distributed. Insomnia is not fun!
W 10/19 -- Problem 5 on the first test was discussed. The tests should be graded and returned, either on F or M. HW 7 won't be out until F 10/21, and will be due F 10/28. We started to discuss the order of numbers mod m, with a goal of determining primitive roots.
First test will be Tuesday evening, October 18, (not 19)
7:00-8:30 pm in Room 147 (not 141!) Altgeld Hall
A student writes: In question 3, HW 5, the polynomial is : x^3 -
9x^2 +23x - 15. You factored it into:
> (x-1)(x-3)(x-5). How?
My reply: Two answers: the sum of the coefficients is 0, which means
that 1 is a
root, so (x-1) is a factor, and the other factor is x^2 - 8x + 15, which
you can do. Second: the polynomial was factored in the previous problem in
the book.
A student writes: In question 7 of HW 5, you take the polynomial
x^3 +4x +8 and turn it into x^3 + x +2. I realize you divided out the
four, but what about the x^3 term?
My reply: I didn't divide by 4, I was reducing mod 3: 1 = 4 and 2 = 8
mod 3.
A student writes: On the first day of class you said that we will soon be
able to calculate the last three digits of 453^(2005). Are we
at the point to do so yet? I know we can compare the last k
digits of a and b with a = b mod 10^(k), but how does that
apply to the aforementioned problem?
My reply:
There's a piece or two still missing, but some tools that we already
have are: (1) The Euler Fermat theorem, as it applies to 2^3 and 5^3
and (2) The Chinese Remainder Theorem I will put this on HW 7; thanks
for reminding me!
M 10/17 -- Homework 6 returned. Review for test (see above). Worked problems, mainly having to do with the Chinese Remainder Theorem. There will be class on W 10/19, with new material, etc.
F 10/14 -- Homework 6 solutions distributed, along with a handout of notes on the Hensel lemma, lyrics to Tom Lehrer's "New Math" (which was played at the end of class) and some further notes on the Catalan numbers.
W 10/12 -- More on addition to base d, and an introduction to the Hensel lemma, and lifting solutions to polynomial congruences from mod p^j to mod p^{j+1}. HW 6 is due Friday. There is no HW due next week, and Friday's class will conclude with a musical interlude.
M 10/10 -- Homework 5 was returned, with a retrospective page, and with a 6-page handout on the material discussed on 10/7, plus elementary estimates on pi(n). On HW 6. the two formulas for the power of 2 dividing C(2n,n) are the one from De Polignac and the one from counting the number of carries.
F 10/7 -- A Missing "/H1" command messes up the rest of the page and was subsequently fixed. More on carries and odd binomial coefficients and even more on pi(n). The Sixth Homework was distributed.
W 10/5 -- Homework 4 returned, along with the retrospective, and a 4-page handout on base d representations and a little bit about bounds on pi(n).
M 10/3 -- Some discussion of Homework 4, a beginning of the representation of integers to base d, and the connection to the prime factorization of binomial coefficients.
F 9/30 -- Homework 4 was collected and discussed. We talked a little more about the Euler phi function and moved on to the prime factorization of n!, for which there will be notes out on M 10/3 (or W 10/5). And the Fifth Homework was distributed.
Questions on HW 4, from the e-mailbag:
Q1. How is the binomial theorem used in #4?
A1. It's used to show that a divides 1 - (1 - a*x1)^s.
Q2. A few questions about the techniques used to
solve congruences of the higher orders (x^3+ ....)
A2. In the one cubic congruence, there are no "techniques"; just calculate
the cubic polynomial for the values mod 9 and mod 5. If you do this right,
you don't have to separately do it mod 45. Also, 1 is evidently a root of
x^3 + 2x - 3, so x - 1 is a factor. This may simplify the work a bit.
Q3. Could explain how they chose a1 (= 4, 13, & 22) and a2 (= 0 & 6)
in Example 6 of section 2.3?
A3. This is a funny example. It is "given" that the values of a1 and a2
are what they are. These are found by working out the polynomial mod 27
and mod 7. I'll try to incorporate this into my presentation on Friday.
Q4. ..and maybe how they arrived at the coefficients 28 and 27
A4. The values 28 and 27 come from the fact that
28 = 1 mod 27
28 = 0 mod 7
-27 = 0 mod 27
-27 = 1 mod 7
and the proof of the Chinese Remainder Theorem.
W 9/28 -- HW 3 was returned, graded, and additional comments were given. The importance in believing what you say when you write a proof was stressed. We spent some time talking about the Euler phi function, and the instructor indulged in rambling reminiscences about his old poetry papers.
M 9/26 -- HW 4 has a typo, which is corrected in Fourth Homework , by adding another smallish part to problem 9. We talked about the Chinese Remainder Theorem and worked many numerical examples.
The Fourth Homework is now available from this page. It will be distributed in class on Monday.
F 9/23 -- HW 2 was returned. HW3 is due on M 9/26. I promised to have HW 4 ready by the end of today, but since I'd probably make a lot of typos, I'll push this back to Sun. afternoon. My apologies if this ruins your weekend plans. Today, we started talking about the Chinese Remainder Theorem, with lots of examples.
W 9/21 -- Sorry this wasn't ready until 9/23. In this class, we finished up on sums of two squares, for now, and started looking at solutions of the congruential equation ax = b mod m.
M 9/19 -- Back from Austria. HW 2 collected and solutions were distributed. We proved Theorems 2.12 and 2.13 from the book and are ready for the full characterization of integers that can be written as a sum of two squares of integers. Anecdotes were presented and chocolates were distributed. It's good to be back home.
F 9/9 -- Sorry this wasn't written before the trip. We went through part of section 2.1 on complete and reduced residue systems, together with the implications for inverses mod m, Euler's generalization of Fermat's Theorem and Wilson's Theorem. Numerical examples were given. The Third Homework was distributed.
A student writes: I don't quite understand the complete residue
system, if it is a defined set of integers or if we can use
variables in the set. The example you gave in class where
m=5 is {0,1...,m-1}. Can we use m in the set of integers? Do
you think you can give me another example of it besides the
example you gave in class.
My reply: I will
talk about complete residue sets more on Friday. Here are 6
examples of complete residue sets mod 5:
0 1 2 3 4
1 2 3 4 5
2 4 6 8 10
3 6 9 12 15
0 4 8 12 16
-18 -11 11 18 2005
(The last is because 2005 = 0 mod 5, 11 = 1 mod 5, -18 = 2 mod 5, 18 = 3
mod 5 and -11 = 4 mod 5. My typewriter doesn't have ='s with three lines,
but it should be there. Remember that "a = b mod m" is a synonym for
"m divides b - a".)
W 9/7 -- Important news! I will be out of town next week, in Austria -- see Workshop Website and class will not meet! We will either have evening exams or extra class sessions to make up for my absence. I will not have a substitute instructor. Also, HW 2 is now due M 9/19, which is the first class period after I get back. HW3 will be distributed on Friday, and due F 9/23. Mathematically, I returned HW 1, distributed supplemental comments and talked about what's important (and what's not important) in proofs. We started chapter 2 on modular arithmetic and finished with Fermat's Little Theorem.
F 9/2 -- HW 1 was collected, solutions were distributed (handwritten,
not available online) and the Second Homework
was distributed. It's due 9/9. I also distributed the phone/email list
and gave a notations handout (neither is available online.) I gave
some applications of the FTA to gcd and lcm. I also gave the oldest
proof in the book and proved something rather obscure (apparently)
about the common factors of the various 2^(2^n)+1's. I'll return to
that on 9/7.
W 8/31 -- I reported that the book was in the bookstore, if not
on the shelves and was informed that it's now on the shelves. We
talked more about gcd, proved the Fundamental Theorem of Arithmetic,
and introduced the notation for the power of a prime that divides a
number: vp(n). (Actually, it's the Greek letter nu, not v,
but I don't know how to write this easily in html.)
In addition to HW2 and the solutions to
HW1, I will give a notations handout on F 9/2.
M 8/29 -- A few questions were answered about the homework: for
undergrads, it will be "10 problems to solve 7". You can earn credit
on all 10, but the denominator will be 7; it's only 10 for grad
students taking the course for 4 hrs credit. A handwritten hand-out
illustrating gcd(453,2005) and the Euclidean algorithm. We have moved
into section 1.3. Next stop: The Fundamental Theorem of Arithmetic.
F 8/26 -- The text hasn't arrived at the Bookstore, so I distributed
sections 1.1 through 1.3. I also passed out a problem solving template
, which is taken from George Polya's great book "How to solve it",
on problem-solving. I covered the definition of gcd and essentially
through Theorem 1.10 (not 1.9). On Monday, we'll see some numerical
examples of the gcd. The First Homework
was distributed, and is due next Friday.
W 8/24 -- First day of class. Two handouts:
Course
Organization, and Math 453
Syllabus.
The book is Niven, Zuckerman and Montgomery (see syllabus), which
should be at the Bookstore soon. I started with Theorems 1.1 and 1.2:
the basic properties of divisibility.