Difference between revisions of "Math 567 -- Elementary Number Theory"
Line 72: | Line 72: | ||
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 19''': Problem A. | + | * '''Oct 19''': Problem A. Using p = 23 and q=31, show how to encrypt the message x=240 with Rabin's algorithm. Find all possible decryptions of your encrypted message. |
− | Problem B. | + | Problem B. Give a prime factorization of the Gaussian integer 7+9i. |
− | + | Problem C. Read the notes from [http://www.math.ucsd.edu/~jverstra/Gaussian1.pdf here]. Note that Z[i] satisfies a ''reduction theorem'': if n and d are Gaussian integers, then there exists integers q and r such that n = qd + r and Norm(r) < Norm(d). But (by contrast with the case of Z) this d may not be unique. In some contexts it is better to be able to choose r uniquely, even if this means letting r have norm greater than Norm(d). | |
+ | |||
+ | C.1. When d = 1+2i, show that, for each n in Z[i], there is a '''unique''' pair (q,r) in Z[i] such that n = qd+r and r is contained in the set {0,1,2,3,4}. For instance, i can be written as i(1+2i) + 2, so we say i reduces to 2 mod (1+2i). | ||
(Hint: Suppose q(1+2i)+r = q'(1+2i) + r'. What can we say about (r-r'), and why is this incompatible with both r and r' being in {0,1,2,3,4}? | (Hint: Suppose q(1+2i)+r = q'(1+2i) + r'. What can we say about (r-r'), and why is this incompatible with both r and r' being in {0,1,2,3,4}? | ||
− | + | C.2. Show that if n is an integer in Z, the reduction of n mod (1+2i) is equal to its reduction mod 5. | |
− | Problem | + | Problem D. Let's try to figure out how to define "phi(d)" for a Gaussian integer d. Suppose S is a set of Gaussian integers such that every n in Z[i] can be written uniquely as qd+r, with q in Z[i] and r in S. (So for instance when d=1+2i, we showed in problem B that we can take S to be {0...4}. It would also be OK to take S to be {1..5} or {0,i,2i,1+i,1+2i}. In fact, it turns out that S has to be a set of size Norm(d) (I might or might not prove this in class; if not, feel free just to accept it.) |
Now define phi(d) to be the number of elements s of S such that s and d are coprime. | Now define phi(d) to be the number of elements s of S such that s and d are coprime. | ||
− | + | D.1. Compute phi(1+2i) and phi(3). | |
− | + | D.2. Prove that the value of phi(d) does not depend on the choice of S. | |
− | + | D.3. Prove that every n in Z[i] which is coprime to 3 satisfies n^phi(3) = 1 mod 3; that is, Euler's theorem holds in this case. (You can prove this by direct computation; of course, if you want, you are welcome to prove that Euler's theorem holds for Z[i] in general, adapting the proof in Stein's book or the one we gave in class.) | |
<!-- | <!-- |
Revision as of 09:22, 13 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.
- Oct 19: Problem A. Using p = 23 and q=31, show how to encrypt the message x=240 with Rabin's algorithm. Find all possible decryptions of your encrypted message.
Problem B. Give a prime factorization of the Gaussian integer 7+9i.
Problem C. Read the notes from here. Note that Z[i] satisfies a reduction theorem: if n and d are Gaussian integers, then there exists integers q and r such that n = qd + r and Norm(r) < Norm(d). But (by contrast with the case of Z) this d may not be unique. In some contexts it is better to be able to choose r uniquely, even if this means letting r have norm greater than Norm(d).
C.1. When d = 1+2i, show that, for each n in Z[i], there is a unique pair (q,r) in Z[i] such that n = qd+r and r is contained in the set {0,1,2,3,4}. For instance, i can be written as i(1+2i) + 2, so we say i reduces to 2 mod (1+2i). (Hint: Suppose q(1+2i)+r = q'(1+2i) + r'. What can we say about (r-r'), and why is this incompatible with both r and r' being in {0,1,2,3,4}?
C.2. Show that if n is an integer in Z, the reduction of n mod (1+2i) is equal to its reduction mod 5.
Problem D. Let's try to figure out how to define "phi(d)" for a Gaussian integer d. Suppose S is a set of Gaussian integers such that every n in Z[i] can be written uniquely as qd+r, with q in Z[i] and r in S. (So for instance when d=1+2i, we showed in problem B that we can take S to be {0...4}. It would also be OK to take S to be {1..5} or {0,i,2i,1+i,1+2i}. In fact, it turns out that S has to be a set of size Norm(d) (I might or might not prove this in class; if not, feel free just to accept it.)
Now define phi(d) to be the number of elements s of S such that s and d are coprime.
D.1. Compute phi(1+2i) and phi(3).
D.2. Prove that the value of phi(d) does not depend on the choice of S.
D.3. Prove that every n in Z[i] which is coprime to 3 satisfies n^phi(3) = 1 mod 3; that is, Euler's theorem holds in this case. (You can prove this by direct computation; of course, if you want, you are welcome to prove that Euler's theorem holds for Z[i] in general, adapting the proof in Stein's book or the one we gave in class.)