# number theory I

# Number Theory

Number theory consists of studying the properties of (the set of all) integers. Of special interest here iare the prime numbers (2,3,5,7,11,13,17,...). Many properties can for instance be understood using the fact that every positive natural number uniquely can be factored as a product of prime numbers. Euclid already knew that there infinitely many primes. Because, if finitely many primes are given, none of these divides the number , and so there has to be another prime number.

But how do you recognise whether a given number N is a prime? For large N it will not be reasonable to check for trial division by known primes. It therefore is desirable to find other properties which have to be fulfilled by prime numbers. For every prime number for instance, the number has to be a multib'ple of . This property therefore gives a neccessary condition for a number to be prime. It is not sufficient, however. But it still is a first step in deciding for large numbers whether thy are prime or not.

If you know a number not to be prime, then you face a much more serious obstacle: how can you factorize it? That this problem really is hard is one of the main reasons for many methods of cryptography to be secure. They use (e.g.) a product of two large primes which has to be factored by a potential enemy. If this has to be done by trial division (and up to now there does not exist a faster method in practise) the message to be decrypted will already have seized to be of importance.

Closely relatde again is the question, how regularly the set of primes is distributed amongst the whole numbers. How many primes below do exist? The asymptotic ansewer to this is

. Yet there are many unsolved questions on the distribution of prime numbers.

Prime numbers occur in many other questions very surprisingly. In studying the energy-niveaus of a quadratic membrane one has to decide which numbers can be written as sums of squares. An odd prime

does admit this if and only if it leaves remainder 1 by division through 4: 5 = 4+1, 13 = 9+4, 17 = 16+1, 29=25+4, 37=36+1,41=25+16...

This can be user to show for any natural number math>n</math>, that it can be written as a sum of two squares if and only if every prime of the kind 4k+3 occurs with an even multiplicity in its prime decomposition.

Phenomena of this kind are frequently studied in lectures on elementary number theory. Beyond this horizon there are more specialized lectures, where you learn how to deal with other "rings of integers", where a prime factorization often is not possible. This (for instance) has postponed the soluion of Fermat's last problem some further 150 years, but it opened the door to new insights into th world of numbers. Most problems which are considered by number theorists today are much less easily formulated than Fermat's Problem.

Of course, there still are some very elementary unsolved questions from number theory. For instance, whether every even number can be written as a sum of two primes (Goldbach-conjecture) or whether there are infinitely many pairs of prime numers differing by 2 (twin-prime-conjecture). Maybe it is wise to refrain from attacking those problems; Choquet is said to have maintained the following position: who openly deals with a well-known unsolved problem risks to be commemorated for his failures only.