This course will be a gentle introduction to the basic concepts of number theory: prime numbers, factorization, and congruences.  Using these concepts we will be able to investigate such diverse topics as 2,000-year-old word problems, "casting out nines" to check arithmetical calculations, perpetual calendars, and the Pythagorean Theorem.  A highlight of the course will be a thorough discussion of the RSA (public key) cryptography system, which is still widely used by government and industry.  By the end of the course, students will be able to understand what the RSA system is, how it works, and why it is so difficult to crack.

Use of the Web

Every enrolled student will be given an account on the Mathematics department undergraduate computer lab located in the MSRC building.  The computer lab is open 24 hours a day.  As part of your account, you will have a quota of 100 pages of free printouts.  You may also access the course web page on any public terminal at UBC, or via your own internet connection.

All documents will be posted in PDF format and can be read with the free Acrobat reader.  This software is already installed on the computers in the Math lab.  You may also download the free Acrobat reader at no cost.

Section 101 of Math 312 has a similar course web page.

Evaluation

• Final exam (tentatively scheduled for Thursday, December 13, 3:30-6:00 pm): 50 percent
• Midterm exam (in class on Tuesday, October 23): 30 percent
• Homework: 20 percent

Homework will be assigned on Tuesdays and due the following Tuesday in class. Late homework will not be accepted. Students are allowed to consult one another concerning the homework problems, but your submitted solutions must be written by you in your own words. If two students submit virtually identical answers to a question, both can be found guilty of plagiarism.

Course syllabus

2 Integer Representations and Operations.  § 2.1 Representations of integers.  (Omit § 2.2, § 2.3)

3 Primes and Greatest Common Divisors.  § 3.1 Prime numbers; § 3.2 Greatest common divisors; § 3.3 The Euclidean algorithm; § 3.4 The fundamental theorem of arithmetic; § 3.5 Factorization methods and the Fermat numbers; § 3.6 Linear Diophantine equations.

4 Congruences.  § 4.1 Introduction to congruences; § 4.2 Linear congruences; § 4.3 The Chinese Remainder Theorem; § 4.4 Solving polynomial congruences; § 4.5 Systems of linear congruences.  (Omit § 4.6)

5 Applications of Congruences.  § 5.1 Divisibility tests; § 5.2 The perpetual calendar; § 5.5 Check digits.  (Omit § 5.3, § 5.4)

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.  (Omit § 7.4)

8 Cryptology.  § 8.1 Character ciphers; § 8.2 Block and stream ciphers; § 8.3 Exponentiation ciphers; § 8.4 Public key cryptography; § 8.6 Cryptographic protocols and applications.  (Omit § 8.5)

Miscellaneous topics (as time permits).  § 12.1 Decimal fractions; § 12.2 Finite continued fractions; § 12.3 Infinite continued fractions; § 12.4 Periodic continued fractions; § 13.1 Pythagorean triples.