Math 324

Elementary Number Theory

Fall 2007

Instructor:    Matilde Lalín

Classroom:    CAB 229

Class Times:    Mondays - Wednesdays - Fridays 11:00 - 11:50 No classes on October 8, November 12

Office:    CAB 621

Office hours:   Monday 12:00 - 13:00, Wednesdays 10:00 - 11:00 and by appointment.

Phone:   (780) 492-3613

e-mail:    lalin at ualberta . ca or mlalin at math . ualberta . ca

Text:    K. H. Rosen, Elementary Number Theory and its Applications 5 th edition, Addison-Wesley

Homework: (suggested problems)

Assignments are not to be turned in. "due" means the date solutions will be posted online in WebCT
. The idea is to give you time to think about the problems without the temptation of looking at the solutions.
• We're done with homework. Try to do as much as possible!

You do not need to know Fermat's descent (chap 13.2) for the exams. However, make sure you know how to do the homework problems from chap 13.1 and 13.3
• "due" 11/28: 13.2.14, problems 1,2,3,4,6,7 from final exam Dec 20, 2004, 13.3.11, 13.3.22 optional: 13.2.4, 13.2.6
• "due" 11/21: All the problems in the final exam of Dec 15, 2003 (we did problem 8 in class), 13.1.2, 13.1.4, 13.1.11, 13.1.18
• "due" 11/14: 9.3.8, 9.3.12, 9.3.14, 11.1.10, 11.1.12, 11.1.22, 11.1.36, 11.2.2, 11.2.4, 11.2.6, curiosity: 11.2.13 (this last problem is not required for the class and it's only here for the people who can't sleep unless they see a proof of QR)
• "due" 11/7: 7.4.15, 7.4.17, 9.1.2, 9.1.6, 9.1.14, 9.1.17, 9.2.2, 9.2.9, 9.2.16, 9.3.6, 9.3.7
• "due" 10/31: 7.1.2, 7.1.8, 7.1.26, 7.1.31, 7.1.36, 7.1.46, 7.2.5, 7.2.10, 7.2.11, 7.3.8, 7.3.16, 7.4.2
• "due" 10/17: 6.1.4, 6.1.8, 6.1.12, 6.1.28, 6.1.29, 6.3.6, 6.3.10, 6.3.11, 6.3.12
• "due" 10/10: 4.2.2, 4.2.5, 4.2.10, 4.2.16, 4.3.10, 4.3.12, 4.3.15, 4.3.22, 4.4.1, 4.4.8, 4.4.10
• "due" 10/3: 3.5.41, 3.5.45, 3.6.4, 3.6.20, 3.7.2, 3.7.7, 3.7.16, 3.7.20, 3.7.22, 4.1.7, 4.1.10, 4.1.19, 4.1.22, 4.1.33
• "due" 9/26: 3.3.8, 3.3.22, 3.3.34, 3.3.35, 3.4.2, 3.4.4, 3.4.19, 3.4.25, 3.5.6, 3.5.47, 3.5.54, 3.5.74 challenging: 3.5.48
• "due" 9/19: 1.4.14, 1.4.34, 1.4.35, 1.4.39, 1.4.40, 1.5.8, 1.5.23, 1.5.29, 1.5.34, 3.1.10, 3.1.20, 3.1.16, 3.2.31 challenging: 1.4.41, 1.4.42, 1.5.40

Make sure you understand how to use strong induction, like in problem 1.4.17

Special Announcements:

• 11/23: Good news! In case it wasn't clear: we finish the program today. Everything coming after this is review/curiosities.

To sum up: second midterm is about the problems that we saw in 7.1,7.2, 7.3, 9.1, 9.2, 9.3, 11.1, 11.2, 13.1, 13.3. Best way to study is to do the homework problems, specially the old final exams

Final is about what you studied for the first and second midterms.
• 11/21: Office hours in the final week will be December 10 and December 11 2-4PM. You are welcome to come at other times and ask questions if I'm in my office. Also, you will be able to pick up your second midterm during those office hours.
• 11/19: I've made a mistake at the beginning of today's class when I say that you can express the general Pythagorean triples in a way analogous to the primitive Pythagorean triples. This is true in some cases, but not in general.
• 11/9: The NSERC USRA awards provide stipends to undergraduate students with high academic standings for pursuing research supervised by a professor over the summer months. More info here.

If you like this class, you may consider working with me. Feel free to discuss this at any time. I'm looking for motivated students, so as long as you satisfy the official criteria, I don't mind if you didn't do well in the midterm.
• 10/29: I will be more flexible in how I weight the midterms for the final mark. More info in the new Addendum to syllabus.
• I have finished marking the midterm exam!!!
• I will be out of town October 21-25. I will be here. Dr. Hadi Salmasian will proctor the midterm exam on October 22 and will teach the October 24 class.

IMPORTANT: if you can not write the exam due to an emergency situation, please do contact me via e-mail as soon as possibe.
• 10/12: I am going to have additional office hours on Thursday October 18 3 - 5 PM. The best way to study for the midterm is to do the homework. If you have doubts about the topics that go into the midterm, they are basically everything we covered in class until 10/12 (inclusive). You can check it if you go to Topics covered in class
• 10/5: Just posted an old midterm in WebCT.

Disclosures: 1) My midterm will probably be harder, and 2) The best way to study for the midterm is to do the homework!
• 9/21: The deferred final exam will be on Januray 12, in CAB 273 (the only new piece of information is the place, you knew the date).
• 9/12: Still missing the book? The Bookstore sent in a rush order for 12 additional copies of the book. They expect that the shipment could arrive as early as this Friday.
• 9/12: I have just posted the solutions to the 9-12 assignment in WebCT. Let me know if you have trouble getting it.

Important dates:
• October 22: First Midterm, in class
• December 3: Second Midterm, in class
• December 12 9:00-12:00 : Final Exam in the classroom
• January 12 Deferred Exam, in CAB 273

Topics covered in Class:

• 12/12: Final 9-12 usual place (CAB 229)
• 12/10-11: Office hours 2-4 PM CAB 621 (my office)
• 12/5: Last class with Al Weiss
• 12/3: Second midterm (Hadi Salmasian is proctoring)
• 11/30: review of multiplicative functions. RSA
• 11/28: more problems about primitive roots
• 11/26: course evaluations, review of primitive roots, problems
• 11/23: finish 3.6, four squares, Waring problem
• 11/21: 13:3 we still need to finish Thm 13.6
• 11/14: finish the example, problem 8 in the final exam of 2003
• 11/9: 11.1 when is 2 a quadratic residue?, 11.2, the law of quadratic reciprocity (without proof), examples

Curiosity: 224 proofs of Quadratic Reciprocity
• 11/7: 11.1 from Legendre symbol to Gauss Lemma (included)
• 11/5: rest of 9.3, 11.1 up to Theorem 11.2
• 11/2: rest of 9.2, 9.3 until primitives roots and powers of 2
Curiosities: You may explore more about primitive roots here
• 10/31: rest of 9.1, 9.2 until lemma 9.1
• 10/29: rest of 7.4, 9.1 up to primitive roots

Curiosity: More about the Moebius function
• 10/26: Rest of 7.3, 7.4 up to thm 7.15
• 10/24: GCD of Fibonacci numbers by Dr. Hadi Salmasian

Curiosity: The fact that GCD(F_m,F_n) = F_GCD(m,n) is a general property of the Lucas sequence U_n. Note that 2^n-1 is also such a sequence.
For a proof see here. This link may or may not work depending where you check it. I can print you a copy if you are interested.
I thank Florian Luca for a helpful discussion.
• 10/22: midterm exam! Proctored by Dr. Hadi Salmasian
• 10/19: 7.3 up to Theorem 7.10, review (Hensel's lemma and CRT)
• 10/17: Multiplicative functions, 7.2, definition of perfect numbers from 7.3

Curiosities: Here you can find information about multiplicative functions. In particular, there are tons of examples!
• 10/15: 7.1 (we haven't covered multiplicative functions in general)

Curiosity: You can read more on the Euler's phi function and its amazing properties here.
• 10/12: Examples of Fermat's little thm, 6.3
• 10/10: (more of Hensel's Lemma), 6.1 (except Pollard Factorization Method)

Curiosity: p-adic numbers or what is Hensel's lemma really telling you?
• 10/5: 4.4 (Hensel's Lemma)
• 10/3: 4.3 (except computer arithmetic), beginning of 4.4
• 10/1: finished 4.1, 4.2, some of 4.3
• 9/28: 3.7 (for more than 2 variables), 4.1 (we're missing the last couple of pages).
Curiosities: An interesting application to congruences has to do with perpetual calendars (chapter 5.2 of the book). Here you see how to compute days of the week mentally, so you can amuse your friends (or your NT prof). Hey, how old am I if my birthday is on April 23 and I was born in a Saturday?
• 9/26: rest of 3.6, 3.7 (for two variables)
Curiosities: More on diophantine equations. Feeling lazy? You can use this application of Stanley Burris to solve a linear Diophantine equation in 2 variables. Remember you won't have this on the exam, so you'd better do your homework without using this site :-)
On a different note, I've found this site due to J. Holt and J. Jones, with Java applications that allow you to experiment with many of the topics that we study in this class.
• 9/24: rest of 3.5, 3.6, but we didn't cover how to prove infinitude of primes using Fermat's numbers.
You need Fermat primes for the contructible polygon. (I think I said it wrongly in class).
Curiosities: About Constructible polygons. Here you can join the search for Fermat prime numbers and similar primer numbers!
• 9/21: 3.5 but we didn't finish with "using prime factorization", and we are missing "proof of Dirichlet's thm for 4n+3" and "irrational numbers". We also convered: formula for the number of divisors.
• 9/19: 3.4
We haven't covered Lame's Theorem proof. For the "Expressing GCD as linear combination" we did problem 3.4.25, but the book has other ways. Any way you do the Euclidean Algorithm is fine with me, as long as you do it right and you understand what you're doing.
• 9/17: 3.3
Curiosities: Did you know? The probability of two integers being relatively prime is 6/π2. You can prove this using the Riemann ζ-funcion that we discussed last time. Look here .
• 9/14: 3.2, definition of GCD
Curiosities: A proof of Bertrand's postulate by Erdos.
Look here and here for some million-dollar problems.
• 9/12: 1.5, 3.1 (without Primality proofs)
Curiosities: If you would like to look for big prime numbers, you (or better, your computer) can join the Great Internet Mersenne Prime Search. For anything about primes: Prime Pages. Interested in primality testing? Here is the general story. Here you are told which algorithm you should use to prove primality depending on the circunstances. (We have no yet covered enough in this class to understand all the algorithms).
• 9/5: Introduction to the class, 1.1 Numbers
Curiosities: If you are interested in trascendence of P and e check Lindemann-Weierstrass theorem. A proof for the trascendence of e can be found here

Other Resources:

In no particular order! I'll keep updating this, so let me know of any suggestions!
• A proof of Bertrand's postulate by Erdos.
• Zeta Grid, a project to find zeros of the Riemann ζ-function. (Thanks Tim for the suggestion.)
• The Euler phi function.

Last update: November 7, 2007