## number theory

**-**

## Number Theory

# Number Theory

Famous formulas in number theory

Famous problems in number theory

Fermat’s failed prime number formula

Number theory a branch of mathematics that studies the properties and relationships of numbers. Specifically, it deals with the natural, or counting numbers, including prime numbers. Number theory is important because the simple sequence of counting numbers from one to infinity conceals many relationships beneath its surface.

## Prime and composite numbers

One of the most important distinctions in number theory is between prime and composite numbers. Prime numbers can only be divided evenly (with nothing left over) by 1 and themselves. Prime numbers include 2, 3, 5, 7, 11, 13, 17, and so on to infinity. The number 1 is not considered a prime. All primes are odd numbers except for 2, because any even number can be divided evenly by 2.

A composite number can be divided, or factored, into two or more prime numbers in addition to 1 and itself. Ten is a composite number because it can be divided by 2, 5, 1, and itself. The numbers 2 and 5 are the prime factors of 10. Any whole number that is not a prime is a composite.

One difference between prime and composite numbers is that it takes relatively little time to determine if a number is prime, but far longer to determine the prime factors of a composite number, especially if the composite is very large (100 digits or more). This discrepancy in computation time is important in developing computer security systems.

Prime numbers do not occur in a predictable way. There are sequences of primes which can be partially described in a formula, but sooner or later the formula breaks down. One formula, invented by French philosopher and mathematician Marin Mersenne (1588–1648) is 2^{p}- 1, where p is a prime number. Although this formula generates many primes, it also misses many primes. Another formula, invented by Swiss mathematician and physicist Leonhard Euler (1707–1783), generates prime numbers regularly for the series of consecutive numbers from 0 to 15 and then stops. The formula is x^{2} + x + 17, in which x is any number from 0 to 15.

## Famous formulas in number theory

Number theory is full of famous formulas that illustrate the relationships between whole numbers from 1 to infinity. Some of these formulas are very complicated, but the most famous ones are very simple, for example, the theorem by Fermat below that proves if a number is prime.

## Fermat’s theorem

French mathematician Pierre de Fermat (1601–1665) is one of the most famous number theoreticians in history, but mathematics was only his hobby. Fermat was a judge in France, and he published very little during his life. He did correspond extensively with many leading intellectuals of his day, and his mathematical innovations were presented to these pen pals in his letters.

One of Fermat’s many theorems provides a quick way of finding out if a number is prime. Say n is any whole number, and p is any prime number. Raise n to the power of p, and then subtract n from the result. If p is really a prime number, then the result can be divided evenly by p. If anything is left over after the division, then the number p is not prime. A shorter way of putting this formula is this: n^{p} - n can be divided evenly by p.

Here is a simple illustration of Fermat’s theorem. Let n=8 and p=3. If Fermat’s theorem is right, then 8^{3} - 8 must be divisible by 3. Multiply 8 by itself three times (8× 8× 8): the product is 512. Subtract 8 from 512: the result is 504. Divide 504 by 3: the result is 168. Fermat’s theorem works for any whole numbers that meet the conditions of the formula.

## Gauss and congruence

German mathematician Karl Friedrich Gauss (1777–1855) made many contributions to pure and applied mathematics. He was born to poor parents in Germany. His high intelligence was noticed early and nurtured by his mother and uncle, but his father never encouraged Gauss in his education.

One of Gauss’s most important contributions to number theory involved the invention of the idea of congruence (or agreement) in numbers and the use of what he called “modulos” or small measures or sets of numbers. In effect, his theory of congruence allows people to break up the infinite series of whole numbers into smaller, more manageable chunks of numbers and perform computations upon them. This arrangement makes the everyday arithmetic involved in such things as telling time much easier to program into computers.

Gauss said that if one number is subtracted from another (a - b), and the remainder of the subtraction can be divided by another number, *m,* then a and b are congruent to each other by the number *m.* Gauss’s formula is as follows: *a* is congruent to *b* modulo *c.* For example, 720 - 480 = 240. The remainder, 240, can be divided by 60, 20, 10, and other numbers. However, for this purpose, only 60 will be applied. Using Gauss’s expression, 720 is congruent to 480 by modulo 60. That is, both 720 and 480 are related to a third number (the remainder after 480 is subtracted from 720), which can be multiplied by 60.

In an abstract sense, this computation is related to such everyday arithmetic functions as telling the time of day on a digital watch. When the watch tells the time, it does not say “240 minutes past noon.” It says “4 o’clock” or “4:00.” To express the time of day, the digital watch uses several kinds of modulos (or small measures) that have been used for centuries: 60 minutes in an hour, 12 hours in the a.m. or p.m. of a day, and so on. If the watch says it is 4:00 in the afternoon, then, from one frame of reference, it has subtracted 480 minutes from the 720-minute period between 12 noon to midnight. What remains is 240 minutes past noon. That is, 720 - 480 = 240. The remainder, 240, can be divided evenly by the modulo 60 (and by other numbers which will be ignored).

When one tells the time every day, however, people do not use Gauss’ terminology. Clocks are already divided into modulos and one simply notes the hour and how many minutes come before or after the hour. The importance of Gauss’s congruence theory is that he created the formulas that allowed an immense variety of arithmetic actions to be performed based on different sets of numbers.

## Famous problems in number theory

Number theory is an immensely rich area and it is defined by the important problems that it tries to solve. Sometimes a problem was considered solved, but years later the solution was found to be flawed. One important challenge in number theory has been trying to find a formula that will describe all the prime numbers. To date, that problem has not been solved. Two of the most famous problems in number theory involve Fermat.

## Fermat’s failed prime number formula

Many mathematicians, including Mersenne and Euler, have tried to find a formula that will define all the prime numbers. No one has ever succeeded.

Fermat had one of the most famous failures. He thought that if he squared 2 and then raised the square of 2 to a higher power, which he labeled n (a whole number), then the results would be nothing but primes. His formula looks like this: _{2}2^{n} + 1 = [a prime number]. This formula appeared to work until Leonhard Euler proved it wrong. Euler found that if 5 is substituted for n in the formula _{2}2n + 1, the resulting number is 4,294,967,297, which can be divided equally by 641 and 6,700,417.

## Fermat’s last theorem

Fermat wrote his famous Last Theorem in the margin of a book some time in the late 1630s. He said that the equation x^{n}+y^{n}=z^{n} has no solutions in whole numbers if n is greater than 2. Mathematicians have been trying to prove or disprove this theorem for centuries. Princeton University professor Andrew J. Wiles apparently had proved it correct but later flaws were found in his proof. By late 1994, Wiles thought the flaws had been solved. Wiles announced in June 1992 that he had proved Fermat right. In 1998, Christopher Breuil, Brian Conrad, Fred Diamond, and Richard Taylor proved that Wiles had indeed proved Fermat’s Last Theorem.

## Current applications

Number theory was labeled the Queen of Mathematics by Gauss. For many years, it was thought to be without many practical applications. That situation has changed significantly in the twentieth century with the rise of computers.

Prime and composite numbers play an important role in modern cryptography or coding systems. Huge volumes of confidential information (such as credit card numbers and bank account numbers) and large amounts of money are transferred electronically around the world every day, all of which must kept secret. One of the important applications of number theory is keeping secrets.

Using Fermat’s theorem, a computer can quickly compute if a number-even a large number-is prime. However, once a computer finds out that a number is not prime, it then takes a long time to find out what its factors are, especially if the number is a large composite (say 120 digits long). It can take years on a supercomputer to find the prime factors of large composite numbers.

This time gap between finding out if a number is prime and factoring the primes in a composite number is useful to cryptographers. To create a security system, they invent numerical codes for the letters and characters of a message. Then they use an encoding algorithm (a series of steps to solve a problem) to turn a message into a long number. If the message is more than a certain length, say 100 characters, then the cryptography program breaks the message into blocks of 100 characters. Once the message is translated into a number, the program multiplies the number of an encoded message by a certain prime (which could be a 100-digit number) and by a composite number. The composite number is the product of two prime numbers, which have been randomly selected and which must be in both the encoding algorithm of the sender and the decoding algorithm of the receiver. The prime numbers making up the composite number are usually

### KEY TERMS

**Algorithm** —Method for solving a numerical problem consisting of a series of mathematical steps.

**Composite number** —A number that can be divided into two or more prime numbers in addition to 1 and itself.

**Congruence** —The relationship between two numbers if they have the same remainder when they are divided by a number.

**Cryptography** —The study of creating and breaking secret codes.

**Factors** —Numbers that are multiplied with other numbers to equal a product. In the multiplication of 2 × 2 = 4, each 2 is a factor. In addition, factors are the numbers that result when numbers are divided. For example, 10 and 10 are factors of 100.

**Modulo** —A number by which two other numbers can be divided to give the same remainder.

**Prime numbers** —Numbers that can only be divided evenly by 1 and themselves.

**Product** —The result of multiplying two or more numbers. Six multiplied by 7 gives the product of 42.

**Set** —A set is a collection of things called members or elements of the set. In mathematics, the members of a set will often be numbers.

**Whole numbers** —The positive integers: 1, 2, 3, 4, ....

quite long (100 digits and longer). When the message is transmitted from the sender to the receiver, some of the numbers are made public, but the primes that make up the composite number are kept secret. The decoding algorithm of the authorized person who receives the message only knows them. Anyone who is eavesdropping on the transmission will see many of the numbers, but without the prime numbers from the encoding and decoding programs, it is impossible to decode the message in any reasonable time.

Computer cryptography systems are only one application of number theory. Other formulas of number theory allow computer programs to find out many years in advance what days of the week will fall on what dates of the month, so that people can find out well in advance what day of the week Christmas or the Fourth of July will occur. Many computers have preinstalled internal programs that tell users when they last modified a file down to the second, minute, hour, day of the week, and date of the month. These programs work thanks to the formulas of number theorists.

## Resources

### BOOKS

Burton, David M. *Elementary Number Theory.* Boston, MA: McGraw-Hill Higher Education, 2007.

Reid, Constance. *From Zero to Infinity: What Makes Numbers Interesting.* Wellesley, MA: A.K. Peters, 2006.

Rosen, Kenneth H. *Elementary Number Theory and Its Applications.* 5th ed. Boston, MA: Pearson/Addison-Wesley, 2005.

Schroeder, Manfred Robert. *Number Theory in Science and Communications: With Applications in Cryptography, Physics, Digital Information, Computing, and Self-similarity.* Berlin, Germany, and New York: Springer, 2006.

Stopple, Jeffrey. *A Primer of Analytic Number Theory: From Pythagoras to Riemann.* Cambridge: Cambridge University Press, 2003.

Vinogradov, Ivan Matveevich. *Elements of Number Theory.* Dover Publications, 2003.

Weisstein, Eric W. *The CRC Concise Encyclopedia of Mathematics.* Boca Raton, FL: Chapman & Hall/CRC Press, 2003.

Patrick Moore

## Number Theory

# Number theory

Number theory is the study of natural, or counting numbers, including **prime numbers** . Number theory is important because the simple sequence of counting numbers from one to **infinity** conceals many relationships beneath its surface.

## Prime and composite numbers

One of the most important distinctions in number theory is between prime and composite numbers. Prime numbers can only be divided evenly (with nothing left over) by 1 and themselves. Prime numbers include 2, 3, 5, 7, 11, 13, 17, and so on to infinity. The number 1 is not considered a prime. All primes are odd numbers except for 2, because any even number can be divided evenly by 2.

A composite number can be divided, or factored, into two or more prime numbers in addition to 1 and itself. Ten is a composite number because it can be divided by 2, 5, 1, and itself. The numbers 2 and 5 are the prime factors of 10. Any whole number that is not a prime is a composite.

One difference between prime and composite numbers is that it takes relatively little time to determine if a number is prime, but far longer to determine the prime factors of a composite number, especially if the composite is very large (100 digits or more). This discrepancy in computation time is important in developing computer security systems.

Prime numbers do not occur in a predictable way. There are **sequences** of primes which can be partially described in a formula, but sooner or later the formula breaks down. One formula, invented by Marin Mersenne (1588-1648) is 2p - 1, where p is a prime number. Although this formula generates many primes, it also misses many primes. Another formula, invented by Leonhard Euler (1707-1783), generates prime numbers regularly for the series of consecutive numbers from 0 to 15 and then stops. The formula is x2 + x + 17, in which x is any number from 0 to 15.

## Famous formulas in number theory

Number theory is full of famous formulas that illustrate the relationships between whole numbers from 1 to infinity. Some of these formulas are very complicated, but the most famous ones are very simple, for example, the **theorem** by Fermat below that proves if a number is prime.

## Fermat's theorem

Pierre de Fermat (1601-1665) is one of the most famous number theoreticians in history, but **mathematics** was only his hobby. He was a judge in France, and he published very little during his life. He did correspond extensively with many leading intellectuals of his day, and his mathematical innovations were presented to these pen pals in his letters.

One of Fermat's many theorems provides a quick way of finding out if a number is prime. Say n is any whole number, and p is any prime number. Raise n to the power of p, and then subtract n from the result. If p is really a prime number, then the result can be divided evenly by p. If anything is left over after the **division** , then the number p is not prime. A shorter way of putting this formula is this: np - n can be divided evenly by p.

Here is a simple illustration of Fermat's theorem. Let n = 8 and p = 3. If Fermat's theorem is right, then 83 - 8 must be divisible by 3. Multiply 8 by itself three times (8 × 8 × 8): the product is 512. Subtract 8 from 512: the result is 504. Divide 504 by 3: the result is 168. Fermat's theorem works for any whole numbers that meet the conditions of the formula.

## Gauss and congruence

Karl Friedrich Gauss (1777-1855) has been called the "Prince of Mathematicians" for his many contributions to pure and applied mathematics. He was born to poor parents in Germany. His high intelligence was noticed early and nurtured by his mother and uncle, but his father never encouraged Gauss in his education.

One of Gauss's most important contributions to number theory involved the invention of the idea of congruence (or agreement) in numbers and the use of what he called "modulos" or small measures or sets of numbers. In effect, his theory of congruence allows people to break up the infinite series of whole numbers into smaller, more manageable chunks of numbers and perform computations upon them. This arrangement makes the everyday **arithmetic** involved in such things as telling time much easier to program into computers.

Gauss said that if one number is subtracted from another (*a* - *b*), and the remainder of the **subtraction** can be divided by another number, *m*, then *a* and *b* are congruent to each other by the number *m*. Gauss's formula is as follows: *a* is congruent to *b* modulo *c*. For example, 720 - 480 = 240. The remainder, 240, can be divided by 60, 20, 10, and other numbers. However, for our purposes, we will only focus on 60. Using Gauss's expression, 720 is congruent to 480 by modulo 60. That is, both 720 and 480 are related to a third number (the remainder after 480 is subtracted from 720), which can be multiplied by 60.

In an abstract sense, this computation is related to such everyday arithmetic functions as telling the time of day on a digital watch. When the watch tells the time, it does not say "240 minutes past noon." It says "4 o'clock" or "4:00." To express the time of day, the digital watch uses several kinds of modulos (or small measures) which have been used for centuries: 60 minutes in an hour, 12 hours in the a.m. or p.m. of a day, and so on. If the watch says it is 4:00 in the afternoon, then, from one frame of reference, it has subtracted 480 minutes from the 720 minute period between 12 noon to midnight. What remains is 240 minutes past noon. That is, 720 - 480 = 240. The remainder, 240, can be divided evenly by the modulo 60 (and by other numbers which we will ignore).

When we tell the time everyday, however, we do not use Gauss's terminology. Our clocks are already divided into modulos and we simply note the hour and how many minutes come before or after the hour. The importance of Gauss's congruence theory is that he created the formulas that allowed an immense variety of arithmetic actions to be performed based on different sets of numbers.

## Famous problems in number theory

Number theory is an immensely rich area and it is defined by the important problems that it tries to solve. Sometimes a problem was considered solved, but years later the solution was found to be flawed. One important challenge in number theory has been trying to find a formula that will describe all the prime numbers. To date, that problem has not been solved. Two of the most famous problems in number theory involve Fermat.

## Fermat's failed prime number formula

Many mathematicians, including Mersenne and Euler, have tried to find a formula that will define all the prime numbers. No one has ever succeeded.

Fermat had one of the most famous failures. He thought that if he squared 2 and then raised the square of 2 to a higher power, which he labeled n (a whole number), then the results would be nothing but primes. His formula looks like this: 2n2 + 1 = a prime number. This formula appeared to work until Leonhard Euler proved it wrong. Euler found that if 5 is substituted for n in the formula 22n + 1, the resulting number is 4,294,967,297, which can be divided equally by 641 and 6,700,417.

## Fermat's last theorem

Fermat wrote his famous "Last Theorem" in the margin of a book some time in the late 1630s. He said that the equation xn + yn = zn has no solutions in whole numbers if n is greater than 2. Mathematicians have been trying to prove or disprove this theorem for centuries. Princeton University professor Andrew J. Wiles apparently had proved it correct but later flaws were found in his proof. By late 1994 Wiles thought the flaws had been solved. Wiles announced in June 1992 that he had proved Fermat right. However, it will take several years before other mathematicians will be able to verify Wiles's proof.

## Current applications

Number theory was labeled the "Queen of Mathe matics" by Gauss. For many years it was thought to be without many practical applications. That situation has changed significantly in the twentieth century with the rise of computers.

Prime and composite numbers play an important role in modern cryptography or coding systems. Huge volumes of confidential information (credit card numbers, bank account numbers) and large amounts of money are transferred electronically around the world every day, all of which must kept secret. One of the important applications of number theory is keeping secrets.

Using Fermat's theorem, a computer can quickly compute if a number-even a large number-is prime. However, once a computer finds out that a number is not prime, it then takes a long time to find out what its factors are, especially if the number is a large composite (say 120 digits long). It can take years on a supercomputer to find the prime factors of large composite numbers.

This time gap between finding out if a number is prime and factoring the primes in a composite number is useful to cryptographers. To create a security system, they invent numerical codes for the letters and characters of a message. Then they use an encoding **algorithm** (a series of steps to solve a problem) to turn a message into a long number. If the message is more than a certain length, say 100 characters, then the cryptography program breaks the message into blocks of 100 characters. Once the message is translated into a number, the program multiplies the number of an encoded message by a certain prime (which could be a 100 digit number) and by a composite number. The composite number is the product of two prime numbers, which have been randomly selected and which must be in both the encoding algorithm of the sender and the decoding algorithm of the receiver. The prime numbers making up the composite number are usually quite long (100 digits and longer). When the message is transmitted from the sender to the receiver, some of the numbers are made public, but the primes that make up the composite number are kept secret. They are only known by the decoding algorithm of the authorized person who receives the message. Anyone who is eavesdropping on the transmission will see a lot of numbers, but without the prime numbers from the encoding and decoding programs, it is impossible to decode the message in any reasonable time.

Computer cryptography systems are only one application of number theory. Other formulas of number theory allow computer programs to find out many years in advance what days of the week will fall on what dates of the month, so that people can find out well in advance what day of the week Christmas or the Fourth of July will occur. Many computers have preinstalled internal programs that tell users when they last modified a file down to the second, minute, hour, day of the week, and date of the month. These programs work thanks to the formulas of number theorists.

## Resources

### books

Davenport, Harold. *The Higher Arithmetic: An Introduction to the Theory of Numbers.* 6th ed. Cambridge: Cambridge University Press, 1992.

Dunham, William. *The Mathematical Universe.* New York: John Wiley and Sons, 1994.

Peterson Ivars, *The Mathematical Tourist: Snapshots of Modern Mathematics.* New York: W.H. Freeman and Company, 1988.

Rosen, Kenneth. *Elementary Number Theory and Its Applications.* 4th ed. Boston: Addison-Wesley, 2000.

Stopple, Jeffrey. *A Primer of Analytic Number Theory: From**Pythagoras to Riemann.* Cambridge: Cambridge University Press, 2003.

Vinogradov, Ivan Matveevich. *Elements of Number Theory.* Dover Publications, 2003.

Weisstein, Eric W. *The CRC Concise Encyclopedia of Mathematics.* New York: CRC Press, 1998.

### periodicals

"Finessing Fermat, Again: The Wily Proof may Finally Be Finished." *Scientific American* 272.2 (February 1995): 16.

Patrick Moore

## KEY TERMS

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .**Algorithm**—Method for solving a numerical problem consisting of a series of mathematical steps.

**Composite number**—A number that can be divided into two or more prime numbers in addition to 1 and itself.

**Congruence**—The relationship between two numbers if they have the same remainder when they are divided by a number.

**Cryptography**—The study of creating and breaking secret codes.

**Factors**—Numbers that are multiplied with other numbers to equal a product. In the multiplication of 2 × 2 = 4, each 2 is a factor. Also, factors are the numbers that result when numbers are divided. For example, 10 and 10 are factors of 100.

**Modulo**—A number by which two other numbers can be divided to give the same remainder.

**Prime numbers**—Numbers that can only be divided evenly by 1 and themselves.

**Product**—The result of multiplying two or more numbers. Six multiplied by 7 gives the product of 42.

**Set**—A set is a collection of things called members or elements of the set. In mathematics, the members of a set will often be numbers.

**Whole numbers**—The positive integers: 1, 2, 3, 4...

## Number Theory

# Number theory

Number theory is the study of natural numbers. Natural numbers are the counting numbers that we use in everyday life: 1, 2, 3, 4, 5, and so on. Zero (0) is often considered to be a natural number as well.

Number theory grew out of various scholars' fascination with numbers. An example of an early problem in number theory was the nature of prime numbers. A prime number is one that can be divided exactly only by itself and 1. Thus 2 is a prime number because it can be divided only by itself (2) and by 1. By comparison, 4 is not a prime number. It can be divided by some number other than itself (that number is 2) and 1. A number that is not prime, like 4, is called a composite number.

The Greek mathematician Euclid (c. 325–270 b.c.) raised a number of questions about the nature of prime numbers as early as the third century b.c. Primes are of interest to mathematicians, for one reason: because they occur in no predictable sequence. The first 20 primes, for example, are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, and 71. Knowing this sequence, would you be able to predict the next prime number? (It is 73.) Or if you knew that the sequence of primes farther on is 853, 857, 859, 863, and 877, could you predict the next prime? (It is 883.)

Questions like this one have intrigued mathematicians for over 2,000 years. This interest is not based on any practical application the answers may have. They fascinate mathematicians simply because they are engrossing puzzles.

## Famous theorems and problems

Studies in number theory over the centuries have produced interesting insights into the properties of natural numbers and ongoing puzzles about such numbers. As just one example of the former, consider Fermat's theorem, a discovery made by French mathematician Pierre de Fermat (1601–1665). Fermat found a quick and easy way to find out if a particular number is a prime or composite number. According to Fermat's theorem, one can determine if any number (call that number *p* ) is a prime number by the following method: choose any number (call that number *n* ) and raise that number to *p*. Then subtract *n* from that calculation. Finally, divide that answer by *p*. If the division comes out evenly, with no remainder, then *p* is a prime number.

Fermat was also responsible for one of the most famous puzzles in mathematics, his last theorem. This theorem concerns equations of the general form x^{n} + y^{n} = z^{n}. When n is 2, a very familiar equation results: x^{2} + y^{2} = z^{2}, the Pythagorean equation of right-angled triangles.

The question that had puzzled mathematicians for many years, however, was whether equations in which n is greater than 2 have any solution. That is, are there solutions for equations such as x^{3} + y^{3} = z^{3}, x^{4} + y^{4} = z^{4}, and x^{5} + y^{5} = z^{5}? In the late 1630s, Fermat wrote a brief note in the margin of a book saying that he had found proof that such equations had no solution when n is greater than 2. He never wrote out that proof, however, and for more than three centuries mathematicians tried to confirm his theory.

As it turns out, any proof that Fermat had discovered was almost certainly wrong. In 1994, Princeton University professor Andrew J. Wiles announced that he had found a solution to Fermat's theorem. But flaws were soon discovered in Wiles's proof (which required more than 150 pages of mathematical equations). By late 1994 Wiles thought the flaws had been solved. However, it will take several years before other mathematicians will be able to verify Wiles's work.

## Words to Know

**Composite number:** A number that can be factored into two or more prime numbers in addition to 1 and itself.

**Cryptography:** The study of creating and breaking secret codes.

**Factors:** Two or more numbers that can be multiplied to equal a product.

**Prime number:** Any number that can be divided evenly only by itself and 1.

**Product:** The number produced by multiplying two or more numbers.

## Applications

As mentioned above, the charm of number theory for mathematicians has little or nothing to do with its possible applications in everyday life. Still, such applications do appear from time to time. One such application has come about in the field of cryptography—the writing and deciphering of secret messages (or ciphers). In the 1980s, a number of cryptographers almost simultaneously announced that they had found methods of writing ciphers in such a way that they could be sent across public channels while still remaining secrets. Those methods are based on the fact that it is relatively easy to raise a prime number to some exponent but very difficult to find the prime factors of a large number.

For example, it is relatively simple, if somewhat time-consuming, to find 358^{143}. Actually, the problem is not even time-consuming if a computer is used. However, finding the prime factors of a number such as 384,119,982,448,028 is very difficult unless one knows one of the prime factors to begin with. The way public key cryptography works, then, is to attach some large number, such as 384,119,982,448,028, as a "key" to a secret message. The sender and receiver of the secret message must know one of the prime factors of that number that allows them to decipher the message. In theory, any third party could also decipher the message provided that they could figure out the prime factors of the key. That calculation is theoretically possible although, in practice, it takes thousands or millions of calculations and a number of years, even with the most powerful computers now known.

## number theory

number theory, branch of mathematics concerned with the properties of the integers (the numbers 0, 1, -1, 2, -2, 3, -3, …). An important area in number theory is the analysis of prime numbers. A prime number is an integer *p*>1 divisible only by 1 and *p*; the first few primes are 2, 3, 5, 7, 11, 13, 17, and 19. Integers that have other divisors are called composite; examples are 4, 6, 8, 9, 10, 12, … . The fundamental theorem of arithmetic, the unique factorization theorem, asserts that any positive integer *a* is a product (*a* = *p*_{1} · *p*_{2} · *p*_{3} · · · *p*_{n}) of primes that are unique except for the order in which they are listed; e.g., the number 20 is the product 20 = 2 · 2 ·5, and it is unique (disregarding order) since 20 has this and only this product of primes. This theorem was known to the Greek mathematician Euclid, who proved that there are infinitely many primes. Analytic number theory has given a further refinement of Euclid's theorem by determining a function that measures how densely the primes are distributed among all integers. Twin primes are primes having a difference of 2, such as (3,5) and (11,13). The modern theory of numbers made its first great advances through the work of Leonhard Euler, C. F. Gauss, and Pierre de Fermat. It remains a major area of mathematical research, to which the most sophisticated mathematical tools have been applied.

See O. Ore, *Number Theory and Its History* (1988); R. P. Burn, *A Pathway into Number Theory* (2d ed. 1996); J. H. Silverman, *A Friendly Introduction to Number Theory* (1996); M. A. Herkommer, *Number Theory: A Programmer's Guide* (1998); R. A. Mollin, *Algebraic Number Theory* (1999).

## number theory

**number theory** Branch of mathematics concerned with the properties of natural numbers (whole numbers) or special classes of natural numbers such as prime numbers and perfect numbers. The 4th-century bc Greek mathematician Euclid proved that the number of primes was infinite. One of the unresolved problems in number theory is to find formulae for the generation of the primes. Fermat (in the 17th century) and Euler (in the 18th century) both explored number theory.