# Number Theory

Number theory explores the arithmetic of the integers, especially problems associated with divisibility. Prime numbers, having no non-trivial divisors, are especially important, yet often it is very difficult to prove theorems about them.

Diophantine equations are those where we want to find integer solutions, if there are any. The most famous of these, Fermat's Last Theorem, involves the equation x^{n} + y^{n} = z^{n}. For n > 2 it has no positive solutions. Although Fermat was convinced of the truth of this statement in the 18^{th} century it has taken till the end of the 20^{th} century for a proof to be found, a proof moreover that requires tools beyond the borders of number theory itself.

We discuss linear equations ax + b = 0 and quadratic equation ax^{2} + bx + c = 0 in **Z**_{n}. The latter involves knowing which numbers have integer square roots in **Z**_{n}.

To answer the latter question we develop the theory of quadratic residues. We define the Legendre function by: (n | m) = 0 if n is a square in **Z**_{m} and 0 otherwise. By developing a large number of properties of this function, some trivial, others quite deep, we can compute (n | m) for large m far more quickly than just by squaring every element.

[Please note that all links are to Adobe .pdf documents. They will open in a separate browser window.]

- Introduction and Contents
- CHAP01 Divisibility
- CHAP02 Linear Congruences
- CHAP03 Quadratic Congruences
- CHAP04 Sums of Squares
- CHAP05 Distribution of Primes
- CHAP06 Power Congruences
- CHAP07 Mersenne and Fermat Primes
- CHAP08 Multiplicative Functions