number theory

A part of pure mathematics that is concerned with the relationships between integers, especially primes and divisibility. Number theory turns out to be unexpectedly significant in the real world, because it has profound significance to cryptography through algorithms such as RSA.

"Number theory," he said, "is the theory of numbers."

The numbers

In number theory, the set of numbers in question is often the rationals or naturals. Real or complex numbers are the work of real or complex analysis. Primes are of particular interest, and a lot of work in number theory is the study of primes and how to prove that a number is or is not prime (see also: The Node of Prime).

The theory

The fundamental theorem of arithmetic says that every natural number is uniquely expressible as a product of powers of distinct primes. This, along with the concepts of divisibility (see also division algorithm) and factorization, are the initial foundations that are often laid in any number theory course.

Built upon these basics are the Euclidean algorithm, studies of linear Diophantine equations, congruences, systems of congruences (a cousin to systems of linear equations), the Chinese Remainder Theorem, multiplicative orders, and many more. Aside from divisibility and factorization, congruences are the most important basic ground to cover; every congruence is a simplified form of a linear Diophantine equation (notationally), and congruences can be shown to have all the properties of equations, aside from some trickiness when it comes to division.

The major branches of number theory are analytic and algebraic, e.g., the prime number theorem is an analytic result, whereas Fermat's little theorem is an algebraic result.

Some well-known results of number theory

• Definition: a divides b (a|b) iff there exists an integer c such that a*c=b.
• Definition: d=gcd(a,b) is the largest integer such that d|a and d|b.
• Definition: a is congruent to b modulo n (a=b(mod n)) iff n|(b-a).
• Theorem: arithmetic of congruence classes is well-defined. In other words, if a=b(mod n) and c=d(mod n), then a+c=b+d(mod n) and a*c=b*d(mod n).
• Wilson's theorem: -1=(n-1)!(mod n) iff n is prime (I used a 'reversed' notation here to avoid confusion between n! (n factorial) and n!= (n does not equal)).
• (note that this is not a complete list; there are additive orders, multiplicative inverses, additive inverses, multiplicative orders, and lots of other theorems...)

Source: the number theory course I took, whose book was:
Holt, Jeffrey J. Discovering Number Theory. W. H. Freeman: New York. 2000.