Mathematics 312, Introduction to number theory, Section 101,
Fall 2015, MWF 11-11:50, Leonard S. Klinck (LSK) Building.

  • Textbook : K. Rosen, Elementary Number Theory, 6th edition.
  • Course syllabus : This course is intended as an introduction to the basic concepts of number theory, such as prime numbers, factorization, and congruences, as well as some of their applications, particularly to cryptography. Proofs are integral to the subject, they will be given in class and problems involving proofs will appear on the homework and on the tests. Regular reading and working through problems from the text are an essential part of the course.

    Wednesday, September 9. Lecture 1. A brief history of number theory. The well-ordering principle and mathematical induction. Slides from Lecture 1.

    Friday, September 11. Lecture 2. Strong mathematical induction (section 1.3). Divisibility (section 1.5). Slides from Lecture 2.

  • Monday, September 14. Lecture 3. Divisibility (section 1.5), prime numbers (section 3.1), greatest common divisor (section 3.3). Notes from Lecture 3 by Prof. Vatsal

    Wednesday, September 16. Lecture 4. Greatest common divisor (section 3.3), the Euclidean algorithm (section 3.4) Slides from Lecture 4

    Friday, September 18. Lecture 5. The Euclidean algorithm (section 3.4), fundamental theorem of arithmetic (section 3.5). Slides from Lecture 5

    Monday, September 21. Lecture 6. Linear diophantian equations (section 3.7). Slides from Lecture 6

    Wednesday, September 23. Lecture 7. Conguences (section 4.1). Notes from Lecture 7 by Prof. Vatsal

    Friday, September 25. Lecture 8. "Unfinished business" on linear diophantian equations (section 3.7), congruences (section 4.1). Notes from Lecture 8

    Monday, September 28. Lecture 9. Representation of integers (section 2.1), repeated squaring (section 4.1). Notes from Lecture 9

    Wednesday, September 30. Lecture 10. Linear congruences (section 4.2). Notes from Lecture 10

    Friday, October 2. Lecture 11. Inverses mod m (section 4.2), Chinese remainder theorem (section 4.3). Notes from Lecture 11

  • Homework : Homework assignments will be collected in class on Fridays, usually on a weekly schedule. Homework problems will ask students to apply theorems from class to carry out calculations, and also to write their own proofs. While homework assignments only count for a fairly small percentage of the total course mark, they are, arguably the most important part of the course. You need to do them in a regular basis to practice, absorb and internalize the material in a way that cannot be replicated by just listening to the lectures or last-minute cramming for exams. Please allow yourself plenty of time to carefully work through each homework assignment, and don't get behind!
    A portion of each assignment will be graded by the course marker. Late homework will not be accepted. Students are allowed to consult one another concerning the homework problems. However, your submitted solutions must be written by you in your own words.

    Homework problems and solutions

    Tips for writing solutions to mathematics problems

  • Evaluation : Course marks will be based on the homework (10%), two midterms (20% each) and the final exam (50%). The midterms will be given in class during regularly scheduled class hours, Wednesday, October 14 and Monday, November 16. The final exam schedule for December 2015 will be announced later in the term. Please make sure you do not make travel plans, work plans, etc., without regard to the examination schedule in this class.
    Calculators can be used to solve homework problems. No calculators, books or notes will not be allowed on the exams.
  • Missed exam policy : There will be no make-up or alternate exams in this class. If you miss a midterm, your score will be recorded as 0, unless you have a serious documented reason (an illness, a death in the family, etc.), in which case you should discuss your circumstances with me as soon as possible.
    Missed finals are not handled by me or the Mathematics Department. Students with legitimate reasons for missing the final exam should request a ``Standing Deferred" status through their faculty.
  • Sections in the book to be covered. Some changes during the term are possible.

    1. The Integers
    1.3 Mathematical induction 1.3
    1.5 Divisibility 1.5

    2. Integers representations and operations
    2.1 Representations of integers.

    3 Primes and Greatest Common Divisors
    3.1 Prime numbers
    3.2 The distribution of primes
    3.3 Greatest common divisors
    3.4 The Euclidean algorithm
    3.5 The fundamental theorem of arithmetic
    3.7 Linear Diophantine equations

    4 Congruences.
    4.1 Introduction to congruences
    4.2 Linear congruences
    4.3 The Chinese Remainder Theorem

    5 Applications of Congruences
    5.1 Divisibility tests
    5.2 The perpetual calendar (will not be covered on final exam)
    5.5. Check digits (ISBN code only)

    6 Some Special Congruences
    6.1 Wilson's Theorem and Fermat's Little Theorem
    6.2 Pseudoprimes
    6.3 Euler's Theorem

    7 Multiplicative Functions
    7.1 The Euler phi-function
    7.2 The sum and number of divisors
    7.3 Perfect numbers and Mersenne primes

    8 Cryptology.
    8.1 Character ciphers
    8.4 Public key cryptography
    8.6 Cryptographic protocols and applications (digital signatures only)

    If time permits, additional topics from Chapters 9, 10 or 11.