Math 25

Number Theory
Last updated June 20, 2019 07:54:46 EDT

Course Objectives: This is a course in what is referred to as Elementary Number Theory. The word "Elementary" is being used in a technical sense to mean the purpose of this course is to study properties of the integers and their applications without using sophisticated tools from abstract algebra (Algebraic Number Theory), or complex analysis (Analytic Number Theory).

You might ask what there could possibly be to study about the integers (that you don't know already), but the subject is vast, provides connections to many other areas of mathematics, and provides the tools of modern cryptography. In part, we want to develop these tools and techniques with a good deal of care so that they will form a foundation on which other courses, especially abstract algebra, can build. The subject of number theory also makes possible a gentle introduction to writing formal mathematical proofs. It begins to provide a rigorous foundation for your mathematical career by proving rigorously many results you have known and used for a long time.

A simple example of this is the fundamental theorem of arithmetic, that every integer $n > 1$ factors "uniquely" as a product of primes. This basic theorem leads to many interesting and practical questions. How do I factor a number, and how can I tell if a number is prime? These may seem mundane questions, but their answers are fundamental both to modern cryptograhic schemes as well as the security of those schemes.

We shall study congruences and modular arithmetic, which provides a fundamental example of equivalence relations, as well as an example of a coset space which you will learn about in group theory. We shall talk about discrete logarithms which were the tool of choice of Diffie and Hellman who first proposed a scheme for public-key cryptography, how two parties unknown to each other can establish secure communications, much as you do every time you order something online.

And of course elementary number theory is chocked full of questions easy to state, but often notoriously difficult to solve. Two of these questions are easy to answer; one is not.

  1. Can you find integers $x, y, z$ so that $987654319 = x^2 + y^2 + z^2$?
  2. There is a right triangle with integer sides whose area is 6. Is there a right triangle with rational sides whose area is 5? How about 157?
  3. Show that the last decimal digit of $1! + 2! + 3! + \cdots + 100!$ is the same as the last digit of $1! + 2! + 3! + \cdots + 1000!$. What is that digit? How about the last two digits?