Difference between revisions of "Math 567 -- Elementary Number Theory"
(23 intermediate revisions by 2 users not shown) | |||
Line 3: | Line 3: | ||
Elementary Number Theory''' | Elementary Number Theory''' | ||
− | + | TR 9:30-10:45, Van Vleck B119 | |
− | '''Professor:''' [http://www.math.wisc.edu/~ | + | '''Professor:''' [http://www.math.wisc.edu/~andreic/ Andrei Caldararu] (andreic@math.wisc.edu) |
− | ''Office Hours:'' | + | ''Office Hours:'' Tuesdays 1:30-3:00, Van Vleck 605. |
− | '''Grader:''' | + | '''Grader:''' Shouwei Hui (shui5@wisc.edu) |
− | ''Office Hours:'' | + | ''Office Hours:'' Wednesdays 3-4pm, Van Vleck 903. |
− | Math 567 is a course in elementary number theory, aimed at undergraduates majoring in math or other quantitative disciplines. A general familiarity with abstract algebra at the level of Math 541 will be assumed, but students who haven't taken 541 are welcome to attend if they're willing to play a little catchup. We will be using William Stein's new (and cheap) textbook [http://www.amazon.com/Elementary-Number-Theory-Computational-Undergraduate/dp/0387855246 Elementary Number Theory: Primes, Congruences, and Secrets], which emphasizes computational approaches to the subject. If you don't need a physical copy of the book, [http://www.williamstein.org/ent/ it is available as a free legal .pdf.] We will be using the (free, public-domain) mathematical software [http://www.sagemath.org/ SAGE], developed largely by Stein, as an integral component of our coursework. There is a [http:// | + | Math 567 is a course in elementary number theory, aimed at undergraduates majoring in math or other quantitative disciplines. A general familiarity with abstract algebra at the level of Math 541 will be assumed, but students who haven't taken 541 are welcome to attend if they're willing to play a little catchup. We will be using William Stein's new (and cheap) textbook [http://www.amazon.com/Elementary-Number-Theory-Computational-Undergraduate/dp/0387855246 Elementary Number Theory: Primes, Congruences, and Secrets], which emphasizes computational approaches to the subject. If you don't need a physical copy of the book, [http://www.williamstein.org/ent/ it is available as a free legal .pdf.] We will be using the (free, public-domain) mathematical software [http://www.sagemath.org/ SAGE], developed largely by Stein, as an integral component of our coursework. There is a [http://doc.sagemath.org/pdf/en/tutorial/SageTutorial.pdf useful online tutorial.] You can download SAGE to your own computer or [http://www.sagenb.org use it online]. |
− | Topics include some subset of, but are not limited to: Divisibility, the Euclidean algorithm and the GCD, linear Diophantine equations, prime numbers and uniqueness of factorization. Congruences, Chinese remainder theorem, Fermat's "little" theorem, Wilson's theorem, Euler's theorem and totient function, the RSA cryptosystem. Number-theoretic functions, multiplicative functions, Möbius inversion. Primitive roots and indices. Quadratic reciprocity and the Legendre symbol. Perfect numbers, Mersenne primes, Fermat primes. Pythagorean triples, Special cases of Fermat's "last" theorem. Fibonacci numbers. Continued fractions. Distribution of primes, discussion of prime number theorem. Primality testing and factoring algorithms. | + | Topics include some subset of, but are not limited to: Divisibility, the Euclidean algorithm and the GCD, linear Diophantine equations, prime numbers and uniqueness of factorization. Congruences, Chinese remainder theorem, Fermat's "little" theorem, Wilson's theorem, Euler's theorem and totient function, the RSA cryptosystem, Rabin's encryption scheme, Diffie-Hellman key exchange protocol. Number-theoretic functions, multiplicative functions, Möbius inversion. Primitive roots and indices. Quadratic reciprocity and the Legendre symbol. Perfect numbers, Mersenne primes, Fermat primes. Pythagorean triples, Special cases of Fermat's "last" theorem. Fibonacci numbers. Continued fractions. Distribution of primes, discussion of prime number theorem. Primality testing and factoring algorithms. |
− | + | '''Course Policies:''' Homework will be due on Thursdays. It can be turned in late only with ''advance'' permission from your grader. It is acceptable to use calculators and computers on homework (indeed, some of it will require a computer) but calculators are not allowed during exams. You are encouraged to work together on homework, but writeups must be done individually. | |
− | '''Course Policies:''' Homework will be due on | + | |
Many of the problems in this course will ask you to prove things. I expect proofs to be written in English sentences; the proofs in Stein's book are a good model for the level of verbosity I am looking for. | Many of the problems in this course will ask you to prove things. I expect proofs to be written in English sentences; the proofs in Stein's book are a good model for the level of verbosity I am looking for. | ||
− | '''Grading:''' The grade in Math 567 will be composed of | + | '''Grading:''' The grade in Math 567 will be composed of 50% homework, 25% midterm, 25% final. The midterm will be on November 9, in class. The final exam date and location will be announced by the University and posted here when available. |
'''Syllabus:''' | '''Syllabus:''' | ||
(This may change as we see what pace works well for the course. All section numbers refer to Stein's book.) | (This may change as we see what pace works well for the course. All section numbers refer to Stein's book.) | ||
− | * Sep | + | * Sep 7 + Sep 11-15: Prime numbers, prime factorizations, Euclidean algorithm and GCD (1.1-1.2) |
− | * Sep | + | * Sep 18-22: The integers mod n, Euler's theorem, the phi function (2.1-2.2) |
− | * Sep | + | * Sep 25-29: Modular exponentiation, primality testing, and primitive roots (2.4-2.5) |
− | * | + | * Oct 2-6: Public-key cryptography and RSA (3.1-3.4) |
− | * Oct | + | * Oct 9-13: Rabin's algorithm (not in the book); algebraic numbers |
− | * Oct | + | * Oct 16-20: Quadratic reciprocity (4.1-4.4) |
− | + | * Oct 23-27: Finite and infinite continued fractions (5.1-5.3) | |
− | * Oct | + | * Oct 31, Nov 2, Nov 7: Continued fractions and diophantine approximation (5.4-5.5) |
− | * Oct | + | * Nov. 9: ''Midterm exam'' |
− | * Nov | + | * Nov 13-17: Diophantine equations I: Pell's equation and Lagrange's theorem |
− | * Nov | + | * Nov 21 and Nov 28-30: Elliptic curves (6.1-6.2) |
− | * | + | * Dec. 4-8: Applications of elliptic curves (6.3-6.4) |
− | + | * Dec. 12: advanced topic TBD: maybe additional discussion of cryptographic techniques? | |
− | * | + | |
− | + | ||
− | + | ||
− | + | ||
'''Homework:''' | '''Homework:''' | ||
− | Homework is due at the beginning of class on the specified | + | Homework is due at the beginning of class on the specified Thursday. Typing your homework is not a requirement, but if you don't already know LaTeX I highly recommend that you learn it and use it to typeset your homework. I will sometimes assign extra problems, which I will e-mail to the class list and include here. |
− | * '''Sep | + | * '''Sep 19''' (note this is Tuesday, not Thursday!): 1.1, 1.3, 1.5, 1.7 (use SAGE), 1.8, 1.14. |
− | Problem A: Use SAGE to compute the number of x in [1..N] such that x^2 + 1 is prime, for N = 100, N = 1000, and N = 10000. Let f(N) be the number of such | + | Problem A: Use SAGE to compute the number of x in [1..N] such that x^2 + 1 is prime, for N = 100, N = 1000, and N = 10000. Let f(N) be the number of such x. |
a) Can you formulate a conjecture about the relationship between f(N) and N/log N? | a) Can you formulate a conjecture about the relationship between f(N) and N/log N? | ||
Line 59: | Line 54: | ||
Note that, despite the evident regularities you'll observe in this problem, we do not even know whether there are infinitely many primes of the form x^2 + 1! You would become very famous if you proved this. | Note that, despite the evident regularities you'll observe in this problem, we do not even know whether there are infinitely many primes of the form x^2 + 1! You would become very famous if you proved this. | ||
− | * '''Sep | + | * '''Sep 28''': 2.6 (the formulation of numerical evidence should be done by Sage if you've got Sage working, and by calculator if not; you can use an online tool like [http://primes.utm.edu/curios/includes/primetest.php this] to test whether a number is prime.) 2.8,2.9,2.11,2.12,2.14,2.19 |
− | + | ||
− | * ''' | + | * '''Oct 5''': 2.15, 2.18, 2.23, 2.26, 2.30. |
Problem A: Prove that if n=pq, with p,q prime, then n is not a Carmichael number. | Problem A: Prove that if n=pq, with p,q prime, then n is not a Carmichael number. | ||
− | + | * '''Oct 12''': Book problems: 3.4, 3.5, 3.6 | |
− | * '''Oct | + | |
− | + | ||
− | Book problems: | + | |
Problem A. Prove that there are infinitely many primes p such that 2 is '''not''' a primitive root in Z/pZ. We break this up into steps. | Problem A. Prove that there are infinitely many primes p such that 2 is '''not''' a primitive root in Z/pZ. We break this up into steps. | ||
+ | |||
Problem A.1. Prove that, if x is an element of Z/nZ, then x^2 is not a primitive root. | Problem A.1. Prove that, if x is an element of Z/nZ, then x^2 is not a primitive root. | ||
+ | |||
Problem A.2. Prove that there are infinitely many primes p such that 2 is a square in Z/pZ. Hint: suppose there are only finitely many such primes p_1, .. p_r, and define N = (p_1 .. p_r)^2 - 2. Where can you go from here...? | Problem A.2. Prove that there are infinitely many primes p such that 2 is a square in Z/pZ. Hint: suppose there are only finitely many such primes p_1, .. p_r, and define N = (p_1 .. p_r)^2 - 2. Where can you go from here...? | ||
+ | |||
Problem A.3. Give a list of five primes p such that 2 is not a primitive root in Z/pZ (you can use the method of this proof or any other.) | Problem A.3. Give a list of five primes p such that 2 is not a primitive root in Z/pZ (you can use the method of this proof or any other.) | ||
Problem B. Prove that 24 is the largest integer n such that every element of (Z/nZ)^* is a root of x^2-1. | Problem B. Prove that 24 is the largest integer n such that every element of (Z/nZ)^* is a root of x^2-1. | ||
+ | <!-- | ||
* '''Oct 8''': | * '''Oct 8''': | ||
Problem A. Give a prime factorization of the Gaussian integer 7+9i. | Problem A. Give a prime factorization of the Gaussian integer 7+9i. | ||
Line 144: | Line 140: | ||
Problem B. When p is a prime congruent to 3 mod 4, prove that ((p-1)/2)! is either 1 or -1 in (Z/pZ). '''OPTIONAL:''' Use sage to compute whether this factorial is 1 or -1 for many primes p. Is there any pattern? Does it seem to be 1 half the time and -1 half the time? Note that I have no idea what the answer to this question is. | Problem B. When p is a prime congruent to 3 mod 4, prove that ((p-1)/2)! is either 1 or -1 in (Z/pZ). '''OPTIONAL:''' Use sage to compute whether this factorial is 1 or -1 for many primes p. Is there any pattern? Does it seem to be 1 half the time and -1 half the time? Note that I have no idea what the answer to this question is. | ||
Problem C. Using the continued fraction expansion, find a solution to the Pell equation x^2 - 13 y^2 = 1. | Problem C. Using the continued fraction expansion, find a solution to the Pell equation x^2 - 13 y^2 = 1. | ||
− | Problem D. Show that the modified Pell equation | + | Problem D. Show that the modified Pell equation x^2 - 7y^2 = -1 has no solutions in integers x,y. (Hint: reduce the equation modulo a suitably chosen prime.) |
Problem E. An ''ideal'' of Z[i] is a subset I of Z[i] which is closed under addition (if x and y are in I, then x+y is in I) and multiplication by Gaussian integers (if x is in i, then zx is also in I for every Gaussian integer z.) The set of multiples of a Gaussian integer is always an ideal (you don't need to prove this.) List all the ideals of Z[i] containing 2Z[i]. (Because such ideals satisfy conditions 1 and 2 from Monday's lecture, this list will be a subset of the list of 5 subgroups we computed in class.) | Problem E. An ''ideal'' of Z[i] is a subset I of Z[i] which is closed under addition (if x and y are in I, then x+y is in I) and multiplication by Gaussian integers (if x is in i, then zx is also in I for every Gaussian integer z.) The set of multiples of a Gaussian integer is always an ideal (you don't need to prove this.) List all the ideals of Z[i] containing 2Z[i]. (Because such ideals satisfy conditions 1 and 2 from Monday's lecture, this list will be a subset of the list of 5 subgroups we computed in class.) | ||
We will not go any further with the notion of ideals in Math 567, but it is worth saying that the language of ideals is absolutely essential for the understanding of contemporary number theory, in a sense "making up for" the failure of unique factorization. | We will not go any further with the notion of ideals in Math 567, but it is worth saying that the language of ideals is absolutely essential for the understanding of contemporary number theory, in a sense "making up for" the failure of unique factorization. | ||
+ | |||
+ | '''November 19''' | ||
+ | |||
+ | Problem A. Using the method discussed in class (which is also the method of problem 4.6 in Stein, which in retrospect I think was too hard to assign with no preparation) find a nontrivial solution with y > 0 to the equation x^2 + 11y^2 = z^2. | ||
+ | Problem B. Let f(X) be the number of solutions of A^2 + B^2 = C^3 such that A^2, B^2, and C^3 are all at most X. Use the heuristic described in class to explain why one might expect f(X) to grow more or less like X^{1/3}. | ||
+ | |||
+ | Problem C. Show that if A+Bi is the cube of a Gaussian integer, then A^2 + B^2 is a perfect cube. | ||
+ | |||
+ | Do ONE of problem D1 and D2; D1 is for people who like Sage, D2 is for people who like proving things. | ||
+ | |||
+ | D1. Use Sage to compute f(X) for X = 1000, 10000, 100000. Does the answer look consistent with the heuristic prediction you made in B? Does f(X)/X^{1/3} appear to be approaching a limit? | ||
+ | D2. We will use problem C to give a lower bound for f(X). Use this to show that there are at least X^{1/3} Gaussian integers with norm at most X that are perfect cubes. From here, show that f(X) > X^{1/3}. | ||
+ | |||
+ | OPTIONAL: Show that the converse of problem C also holds -- A+Bi has norm a perfect cube if and only if A+Bi is a perfect cube. (You will need unique factorization of Gaussian integers.) Using this fact, prove that f(X) is bounded above by C X^{1/3} for some constant C. | ||
+ | |||
+ | '''December 8 (note nonstandard due date)''' | ||
+ | |||
+ | Problem A: Hyperbolas, ellipses, and "magic slopes" | ||
+ | |||
+ | In the usual analytic geometry, both hyperbolas and ellipses are given by equations of the form | ||
+ | |||
+ | ax^2 + bxy + cy^2 = d (*) | ||
+ | |||
+ | |||
+ | (we always assume d is nonzero.) | ||
+ | |||
+ | How can we tell whether such an equation describes an ellipse or a | ||
+ | hyperbola? Well, in the geometric setting we all know and love (i.e. in | ||
+ | R^2) a hyperbola has asymptotes and an ellipse does not. What is an | ||
+ | asymptote? You could say it's "a line which doesn't intersect the curve", | ||
+ | but ellipses have such lines too. You might want to say "a line which | ||
+ | doesn't intersect the curve but comes closer and closer to the curve," but | ||
+ | the problem here is that this a) is somewhat imprecise, and b) relies on a | ||
+ | notion of "closer" that is not going to be very clear in Z/pZ, which is | ||
+ | our ultimate goal! | ||
+ | |||
+ | |||
+ | So let me state it a different way: let's say the asymptotes of a | ||
+ | hyperbola have slopes m_1 and m_2. These are "magic slopes" in the | ||
+ | following sense: ANY line of slope m_1 (and ditto for m_2) intersects the | ||
+ | hyperbola in at most one point. An ellipse doesn't have "magic slopes" -- | ||
+ | you can convince yourself by drawing pictures that, for any slope m, you | ||
+ | can find a line of slope m striking the ellipse twice. | ||
+ | |||
+ | |||
+ | [REMARK: For technical reasons we're going to ignore hyperbolae with a | ||
+ | vertical asymptote, since vertical lines don't exactly have slope.] | ||
+ | |||
+ | |||
+ | Now you might know the criterion that, over the real numbers. | ||
+ | |||
+ | |||
+ | ax^2 + bxy + cy^2 = d | ||
+ | |||
+ | |||
+ | is a hyperbola if b^2 - 4ac > 0 and an ellipse if b^2 - 4ac < 0. (For | ||
+ | instance, x^2 - y^2 = 1 is a hyperbola with magic slopes 1 and -1, and x^2 | ||
+ | + y^2 = 1 is an ellipse.) | ||
+ | This criterion does not make sense in Z/pZ, where there is no notion of | ||
+ | "greater" or "less." | ||
+ | |||
+ | |||
+ | QUESTION A.1. | ||
+ | |||
+ | For which primes p is it the case that | ||
+ | |||
+ | x^2 + y^2 = 1 | ||
+ | |||
+ | has magic slopes in Z/pZ? | ||
+ | |||
+ | QUESTION A.2. For which primes p is it the case that | ||
+ | |||
+ | |||
+ | x^2 - y^2 = 1 | ||
+ | |||
+ | |||
+ | has magic slopes in Z/pZ? | ||
+ | |||
+ | |||
+ | QUESTION B: Back in the very first week of this course we studied the set of integers x such that x^2 + 1 is prime. Based on the heuristics we discussed in class, about how many x between 1 and N would you expect to satisfy "x^2 + 1 is prime?" | ||
+ | |||
+ | |||
+ | QUESTION C: Let z be a complex number. Then the set of all complex numbers of the form a + bz, with a and b integers, forms a lattice in the complex plane (thought of as R^2.) What is the covolume of this lattice, in terms of z? | ||
+ | |||
+ | |||
+ | QUESTION D: Let z be a complex number. Using Minkowski's theorem and the result of question C, show that there exist integers a,b, not both zero, such that Norm(a+bz) is at most (4/pi) Im(z). (Hint: let Omega be the set of all complex numbers of norm at most (4/pi) Im(z).) | ||
+ | |||
+ | |||
+ | OPTIONAL EXTRA: Can you give an exact formula for the minimal norm of any nonzero complex number of the form a+bz? --> |
Revision as of 19:11, 5 October 2017
MATH 567
Elementary Number Theory
TR 9:30-10:45, Van Vleck B119
Professor: Andrei Caldararu (andreic@math.wisc.edu) Office Hours: Tuesdays 1:30-3:00, Van Vleck 605.
Grader: Shouwei Hui (shui5@wisc.edu) Office Hours: Wednesdays 3-4pm, Van Vleck 903.
Math 567 is a course in elementary number theory, aimed at undergraduates majoring in math or other quantitative disciplines. A general familiarity with abstract algebra at the level of Math 541 will be assumed, but students who haven't taken 541 are welcome to attend if they're willing to play a little catchup. We will be using William Stein's new (and cheap) textbook Elementary Number Theory: Primes, Congruences, and Secrets, which emphasizes computational approaches to the subject. If you don't need a physical copy of the book, it is available as a free legal .pdf. We will be using the (free, public-domain) mathematical software SAGE, developed largely by Stein, as an integral component of our coursework. There is a useful online tutorial. You can download SAGE to your own computer or use it online.
Topics include some subset of, but are not limited to: Divisibility, the Euclidean algorithm and the GCD, linear Diophantine equations, prime numbers and uniqueness of factorization. Congruences, Chinese remainder theorem, Fermat's "little" theorem, Wilson's theorem, Euler's theorem and totient function, the RSA cryptosystem, Rabin's encryption scheme, Diffie-Hellman key exchange protocol. Number-theoretic functions, multiplicative functions, Möbius inversion. Primitive roots and indices. Quadratic reciprocity and the Legendre symbol. Perfect numbers, Mersenne primes, Fermat primes. Pythagorean triples, Special cases of Fermat's "last" theorem. Fibonacci numbers. Continued fractions. Distribution of primes, discussion of prime number theorem. Primality testing and factoring algorithms.
Course Policies: Homework will be due on Thursdays. It can be turned in late only with advance permission from your grader. It is acceptable to use calculators and computers on homework (indeed, some of it will require a computer) but calculators are not allowed during exams. You are encouraged to work together on homework, but writeups must be done individually.
Many of the problems in this course will ask you to prove things. I expect proofs to be written in English sentences; the proofs in Stein's book are a good model for the level of verbosity I am looking for.
Grading: The grade in Math 567 will be composed of 50% homework, 25% midterm, 25% final. The midterm will be on November 9, in class. The final exam date and location will be announced by the University and posted here when available.
Syllabus: (This may change as we see what pace works well for the course. All section numbers refer to Stein's book.)
- Sep 7 + Sep 11-15: Prime numbers, prime factorizations, Euclidean algorithm and GCD (1.1-1.2)
- Sep 18-22: The integers mod n, Euler's theorem, the phi function (2.1-2.2)
- Sep 25-29: Modular exponentiation, primality testing, and primitive roots (2.4-2.5)
- Oct 2-6: Public-key cryptography and RSA (3.1-3.4)
- Oct 9-13: Rabin's algorithm (not in the book); algebraic numbers
- Oct 16-20: Quadratic reciprocity (4.1-4.4)
- Oct 23-27: Finite and infinite continued fractions (5.1-5.3)
- Oct 31, Nov 2, Nov 7: Continued fractions and diophantine approximation (5.4-5.5)
- Nov. 9: Midterm exam
- Nov 13-17: Diophantine equations I: Pell's equation and Lagrange's theorem
- Nov 21 and Nov 28-30: Elliptic curves (6.1-6.2)
- Dec. 4-8: Applications of elliptic curves (6.3-6.4)
- Dec. 12: advanced topic TBD: maybe additional discussion of cryptographic techniques?
Homework: Homework is due at the beginning of class on the specified Thursday. Typing your homework is not a requirement, but if you don't already know LaTeX I highly recommend that you learn it and use it to typeset your homework. I will sometimes assign extra problems, which I will e-mail to the class list and include here.
- Sep 19 (note this is Tuesday, not Thursday!): 1.1, 1.3, 1.5, 1.7 (use SAGE), 1.8, 1.14.
Problem A: Use SAGE to compute the number of x in [1..N] such that x^2 + 1 is prime, for N = 100, N = 1000, and N = 10000. Let f(N) be the number of such x.
a) Can you formulate a conjecture about the relationship between f(N) and N/log N?
b) What if x^2 + 1 is replaced with x^2 + 2? Can you explain why x^2 + 2 appears less likely to be prime? (Hint: consider x mod 3.)
c) Prove that f(N) is at most (1/2)N+1. (Hint: consider x mod 2.)
d) Give as good an upper bound as you can for f(N).
Note that, despite the evident regularities you'll observe in this problem, we do not even know whether there are infinitely many primes of the form x^2 + 1! You would become very famous if you proved this.
- Sep 28: 2.6 (the formulation of numerical evidence should be done by Sage if you've got Sage working, and by calculator if not; you can use an online tool like this to test whether a number is prime.) 2.8,2.9,2.11,2.12,2.14,2.19
- Oct 5: 2.15, 2.18, 2.23, 2.26, 2.30.
Problem A: Prove that if n=pq, with p,q prime, then n is not a Carmichael number.
- Oct 12: Book problems: 3.4, 3.5, 3.6
Problem A. Prove that there are infinitely many primes p such that 2 is not a primitive root in Z/pZ. We break this up into steps.
Problem A.1. Prove that, if x is an element of Z/nZ, then x^2 is not a primitive root.
Problem A.2. Prove that there are infinitely many primes p such that 2 is a square in Z/pZ. Hint: suppose there are only finitely many such primes p_1, .. p_r, and define N = (p_1 .. p_r)^2 - 2. Where can you go from here...?
Problem A.3. Give a list of five primes p such that 2 is not a primitive root in Z/pZ (you can use the method of this proof or any other.)
Problem B. Prove that 24 is the largest integer n such that every element of (Z/nZ)^* is a root of x^2-1.