Introduction.

     People created mathematics to meet their practical needs. They introduced integers and fractions, studied their properties.

     Afterwards, mathematicians paid great attention to such problems, solutions of which weren't directly connected with practical demands.

     In the III century B.C. Euclid proved, that the set of the prime numbers is infinite. Eratosthenes invented the Eratosthenes' sieve which helps to pick primes out of the natural row. Later Gauss proved the fundamental theorem of arithmetics about the only factorization of natural numbers into their prime factors. On proving he based himself upon the theorem, which is well known as Gauss theorem : for any two numbers a and b there exists such a couple of integers x and y, that ax + by = d, where d is the greatest common divisor of a and b. The latter theorem is proved with the help of Euclid's algorithm. In the XVII century Fermat proved, that for any prime number p and a, co-prime with it, the a ^p-1- 1is divisible by p. This theorem is known as the small theorem of Fermat. Later Euler generalized it: if j(n) means the quantity of numbers less than n and co-prime with it, than for any a, co-prime with n, a^j(n) - 1 is divisible by n. ( Euler theorem (1)).