# MATH 328K -- INTRODUCTION TO NUMBER THEORY

### General Information

```
Instructor: Dave Rusin (rusin@math.utexas.edu)
Office hrs: T,Th 11-12:15 and T 4:30-6:00 and by appointment, in RLM 9.140 .
(I am usually in my office during ordinary business hours but if you
want to be sure I'm available, let me know in advance.)

Text: Elementary Number Theory and its Applications (Rosen, 6th edition)

This course has Unique ID 54535 and meets T,Th at 12:30pm in BUR134.

Registration in this course is closed; I can't put anyone into
it. If you think you will probably drop the course, please do
so promptly and allow another student to take your place.

Your final exam will be held Monday, May 15, 2:00 PM -- 5:00 PM
There is no provision for taking the final exam earlier or later.
You can always confirm your own exam schedule at the Registrar's web site.
The exam may not be held in the regular classroom; I will announce the
location when I know it.

```

Course webpage: http://www.ma.utexas.edu/~rusin/328K/ It is unlikely that I will post any important material to Canvas; for any additional information I want to give you outside of class you should come to this webpage.

UPDATE:I promised you the details I didn't want to present in class today, showing that the sum of the reciprocals of all primes is infinite. (That says something about how common primes are among all the integers.) Here it is

UPDATE:I will put links to the homework problems I assign, in the appropriate section below.

### Course Description

Number Theory is the study of the properties of the integers and related constructs. We will look at primes and squares and so on, which you have probably known about for years, but watch out! This course progresses very far and fast and you will learn some amazing things about the integers. For example, I will show you how a very large portion of Internet security works, and tell you how you may crack it.

This is a first course that emphasizes understanding and creating proofs; therefore, it must provide a transition from the problem-solving approach of calculus to the entirely rigorous approach of advanced courses such as M365C or M373K. The number of topics required for coverage has been kept modest so as to allow instructors adequate time to concentrate on developing the students theorem-proving skills.

### Pre-requisites

M341 or M325K, with a grade of at least C-.

### Class structure

I would like to use our very limited time together to be more productive by getting you to do things rather than sit passively listening to me drone on and on. We will work individually or in groups, and some of you may present work for the rest of the class to see.

Homeworks: I intend to assign homework problems approximately weekly. By all means work with your friends but you must write up your own work.

I will drop the two lowest homework grades and average the rest to give you a "Homework Score" of up to 100 points for the semester

Here as well are some answers to Test 2

Homework scores will be converted to letter grades using the following scale:
 97-100 A+ 94-96 A 90-93 A- 87-89 B+ 84-86 B 80-83 B- 77-79 C+ 74-76 C 70-73 C- 67-69 D+ 64-66 D 60-63 D- 0-59 F

Exams: There will be 2 mid-term exams, to be held during the usual class period, and a comprehensive final exam.

I will use the scale above to convert your exam raw score to a letter grade, but because my exams tend to be hard, I will also use the following alternative method if it gives you a higher letter grade. After I compute the mean and the standard deviation of the class grades, I will determine how many standard deviations above or below the mean your grade is. If your score is greater than the mean by less than one standard deviation, you will get a B (or B+ or B-, as appropriate); higher scores get A's, lower scores get C's, D's, and F's. For example, suppose the class average on the exam was 78.3 points and the standard deviation was 14.4 points. Then the conversion from raw scores to letter grades will be based on these brackets (of width 14.4/3 = 4.8 up and down from 78.3) :
 *SAMPLE!* 103+ A+ 98-102 A 93-97 A- 88-92 B+ 84-87 B 79-83 B- 74-78 C+ 69-73 C 64-68 C- 60-63 D+ 55-59 D 50-54 D- 0-49 F
In this way I am literally giving grades of "above average" (A's and B's) exactly to students whose scores are above the class average. (Mean is not the same as median; most of my students last semester got A's and B's; only 11% of the letter grades were D's and F's.)

Note that in this example any student whose raw score was 87 or higher would get a higher letter grade based on the traditional 90-80-70-60 scale shown earlier, and thus for those students the more generous scale will be used.

Your final semester grade is simply a weighted average of the components: homework 30%, midterms 20% each, and the final exam 30%. I do the arithmetic as is done for high-school GPAs: A=4.0, B=3.0, etc; "+" and "-" are one-third of a letter grade up or down. An average of 3.83 rounds down to an A- (3.67) while 3.84 rounds up to an A (4.00), etc. Sadly, the university does not permit me to report scores of "A+" but internally I do track those terrific students whose semester average is 4.17 or above!

### Policies

Classroom activity: Our meeting times together are very short so we must make the most of them. Come to class daily and ask questions; this is greatly facilitated by reading ahead each day and doing the homework problems as they are assigned. Please silence your cell phones. I will always assume that any talking I hear is about the course material so I may ask you to share your conversations with the class.

Make-ups: It is in general not possible to make up missing homework assignments after the due date. If you believe you will have to miss a graded event, please notify me in advance; I will try to arrange for you to complete the work early.

Students with disabilities: The University of Texas at Austin provides upon request appropriate academic accommodations for qualified students with disabilities. For more information, contact the Office of the Dean of Students at 471-6259, 471-4641 TTY.

Religious holidays: If you are unable to participate in a required class activity (such as an exam) because it conflicts with your religious traditions, please notify me IN ADVANCE and I will make accommodations for you. Typically I will ask you to complete the required work before the religious observance begins.

Academic Integrity. Please read the message about Academic Integrity from the Dean of Students Office. I very much prefer to treat you as professionals whose honesty is beyond question; but if my trust is violated I will follow the procedures available to me to see that dishonesty is exposed and punished.

Campus safety: Please familiarize yourself with the Emergency Preparedness instructions provided by the university's Campus Safety and Security office. In the event of severe weather or a security threat, we will immediately suspend class and follow the instructions given. You may wish to sign up with the campus alert programs.

Counseling: Students often encounter non-academic difficulties during the semester, including stresses from family, health issues, and lifestyle choices. I am not trained to help you with these but do encourage you to take advantage of the Counselling and Mental Health Center, Student Services Bldg (SSB), 5th Floor, open M-F 8am-5pm. (512 471 3515, or www.cmhc.utexas.edu

Drop dates: Jan 20 is the last day to drop without approval of the department chair; Feb 1 is the last day to drop the course for a possible refund; Apr 3 is the last day an undergraduate student may, with the dean's approval, withdraw from the University or drop a class except for urgent and substantiated, nonacademic reasons.

Computers: Some topics in this course are very well suited to numerical experiments beyond the range of what you can do with pencil and paper. I encourage you to try the biggest and most informative examples you can. You are welcome to use the department's computer facilities. Our 40-seat undergrad computer lab in RLM 7.122, is open to all students enrolled in Math courses. Students can sign up for an individual account themselves in the computer lab using their UT EID. We have most of the mainstream commercial math software: Mathematica, Maple, Matlab, etc., and an assortment of open source programs. If you come to my office you will see me use some of this software to help illustrate concepts. Please see me if you would like more information.

### Schedule

Here is a rough approximation to the timetable of topics, but I reserve the right to adjust this to meet the needs and interests of the class.
• Tuesday, Jan 17: Introduction to number theory, divisiblity, and proofs by definition.
• Thursday,Jan 19: Divisiblity, congruences, and modular arithmetic.
• Tuesday, Jan 24: Congruences, modular arithmetic, and applications.
• Thursday,Jan 26: Greatest common divisors.
• Tuesday, Jan 31: Proofs by induction and greatest common divisors.
• Thursday,Feb 02: Greatest common divisors, linear Diophantine equations, invertible elements, and Chinese remainder theorem.
• Tuesday, Feb 07: Fundamental theorem of arithmetic.
• Thursday,Feb 09: Fermat's little theorem, Wilson's theorem, and applications.
• Tuesday, Feb 14: Euler's phi function and Euler's theorem.
• Thursday,Feb 16: Euler's phi function and other multiplicative functions.
• Tuesday, Feb 21: Moebius inversion and Legendre symbols.
• Thursday,Feb 23: Midterm 1
• Tuesday, Feb 28: Legendre symbols, Euler's criterion, Gauss' lemma
• Thursday,Mar 02: Special cases of the Legendre symbol and quadratic reciprocity
• Tuesday, Mar 07: Proof of quadratic reciprocity and the Jacobi symbol
• Thursday,Mar 09: Quadratic reciprocity for the Jacobi symbol and primitive roots
• Spring Break!
• Tuesday, Mar 21: Primitive roots and Lagrange's theorem
• Thursday,Mar 23: Existence of primitive roots
• Tuesday, Mar 28: Nonexistence of primitive roots and index arithmetic
• Thursday,Mar 30: Power residues, the proof of Chinese remainder theorem, and Hensel's lemma
• Tuesday, Apr 04: The proof of Hensel's lemma and Pythagorean triples
• Thursday,Apr 06: Pythagorean triples and Fermat's last theorem
• Tuesday, Apr 11: Cryptography
• Thursday,Apr 13: The prime number theorem
• Tuesday, Apr 18: Gaussian integers: definition, associates and units, norm, divisiblity, and primes
• Thursday,Apr 20:Midterm 2
• Tuesday, Apr 25: Gaussian integers: division algorithm and greatest common divisors
• Thursday,May 02: Gaussian integers: unique factorization, sums of squares, and classification of primes.
• Tuesday, May 04: Sums of squares, Gaussian primes, and prime number theorems for Gaussian integers
• *** Your final exam will be held Monday, May 15, 2:00 PM -- 5:00 PM ***