Number Theory I INTRODUCTION Number Theory, branch of mathematics that deals with the properties and relationships of numbers (see Number).

Number Theory I INTRODUCTION Number Theory, branch of mathematics that deals with the properties and relationships of numbers (see Number). According to this broad definition, the theory of numbers includes much of mathematics, particularly mathematical analysis. Generally, however, the theory of numbers is confined to the study of integers, or occasionally to some other set of numbers having properties similar to the set of all integers. II NATURE OF INTEGERS If a, b, c are integers such that a = bc, a is called a multiple of b or of c, and b or c is called a divisor or factor of a. If c is not ±1, b is called a proper divisor of a. Even integers, which include 0, are multiples of 2, for example, -4, 0, 2, 10; an odd integer is an integer that is not even, for example, -5, 1, 3, 9. A perfect number is a positive integer that is equal to the sum of all its positive, proper divisors; for example, 6, which equals 1 + 2 + 3, and 28, which equals 1 + 2 + 4 + 7 + 14, are perfect numbers. A positive number that is not perfect is imperfect and is deficient or abundant according to whether the sum of its positive, proper divisors is smaller or larger than the number itself. Thus, 9, with proper divisors 1, 3, is deficient; 12, with proper divisors 1, 2, 3, 4, 6, is abundant. III PRIMES Much of the theory of numbers is devoted to the study of primes. A number p (p ? ±1) is a prime if its only divisors are ±1, ±p . A number a is composite if a = bc, in which neither b nor c is ±1. The first ten positive primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29; the first ten positive composite numbers are 4, 6, 8, 9, 10, 12, 14, 15, 16, 18. A composite number can be factored into a product of primes in only one way, apart from the order of the factors; thus, 9 = 3 × 3; 10 = 2 × 5; 12 = 2 × 2 × 3. The ninth book of the Elements by the Greek mathematician Euclid contains the proof of the proposition that the number of primes is infinite; that is, no largest prime exists. The proof is remarkably simple: let p be a prime and q = 1 × 2 × 3 × ... × p + 1; that is, one more than the product of all the integers from 1 through p. The integer q is larger than p and is not divisible by any integer from 2 through p, inclusive. Any one of its positive divisors, other than 1, and any one of its prime divisors, therefore, must be larger than p. It follows that there must be a prime larger than p. Although the number of primes is infinite, the primes become relatively scarce as one proceeds further and further out into the number system. Indeed, the number of primes between 1 and n, for very large values of n, is approximately n divided by the natural logarithm of n. Twenty-five percent of the numbers between 1 and 100, 17 percent of the numbers between 1 and 1000, and 7 percent of the numbers between 1 and 1,000,000 are primes. Two primes that differ by 2 (for example, 5, 7; 17, 19; 101, 103) are called twin primes. It is not known whether the number of twin primes is infinite. Another conjecture is that every even number greater than 2 can be expressed as the sum of two primes; thus, 4 = 2 + 2; 6 = 3 + 3; 8 = 3 + 5; 10 = 5 + 5; 20 = 3 + 17; 100 = 3 + 97; however, a general proof is still lacking. The greatest common divisor of two integers a and b is the largest positive integer that divides both a and b exactly. Euclid gave a method for finding this greatest common divisor for two integers. If the greatest common divisor of two integers is 1, the two numbers are said to be relatively prime, or one integer is said to be prime to the other. If p, q, ..., u are the distinct prime divisors of a positive integer n, the number of positive integers not exceeding and prime to n is given by the formula If a, b, m are integers (m, positive) such that a - b is a multiple of m, then a is congruent to b with respect to the modulus m, which is written a: b (mod m) This expression itself is called a congruence; congruences behave in many respects like equations. The theory of congruences is very important in number theory; for example, congruence theory can be used to solve problems known as Chinese remainders. An illustrative problem of this type is: Find the first two positive integers having the remainders 2, 3, 2, when divided by 3, 5, 7, respectively. The answer, 23 and 128, was given by the Chinese mathematician Sun-Ts? in the 1st century Contributed By: James Singer Microsoft ® Encarta ® 2009. © 1993-2008 Microsoft Corporation. All rights reserved. AD.