Mutually prime numbers. Basics

Textbooks of mathematics are sometimes difficult to comprehend. The dry and clear language of the authors is not always available for understanding. And the topics there are always interconnected, mutually flowing. To master one topic, you have to raise a number of previous ones, and sometimes even leaf through the entire textbook. Complicated? Yes. And let's dare to bypass these difficulties and try to find to the topic not quite a standard approach. Let's make a digression into the country of numbers. Definition, however, we still leave the same, because the rules of mathematics can not be canceled. So, relatively prime numbers are natural numbers, with a common divisor equal to one. It's clear? Completely.

For a more illustrative example, let's takenumbers 6 and 13. Both are divisible by one (relatively prime). But the numbers 12 and 14 - they can not be those, because they are divided not only into 1, but also to 2. The following numbers - 21 and 47 also do not fit into the category "mutually prime numbers": they can be divided not only by 1, but also on 7.

Denote mutually prime numbers as: (a, y) = 1.

It can even be said more simply: the common divisor (the largest) here is equal to one.
Why do we need such knowledge? There are enough reasons.

Mutually prime numbers are included in someencryption system. Those who work with the ciphers of Hill or with the system of permutations of Caesar, understand: without this knowledge - anywhere. If you have heard about generators of pseudo-random numbers, you are unlikely to dare to deny that relatively prime numbers are also used there.

Now let's talk about ways to get such numbers. Numbers simple, as you understand, can have only two divisors: they are divisible by themselves and by one. Say 11, 7, 5, 3 are simple numbers, but 9 is not, because this number is already divisible by 9, and by 3, and by 1.

And if a - the number is prime, and the - from the set {1, 2, ... a - 1}, then it is guaranteed (a, the) = 1, or relatively prime numbers - a and the.

This is, rather, not even an explanation, but a repetition or summing up of what has just been said.

Getting primes is probably a sieveEratosthenes, however, for impressive numbers (billions, for example) this method is too long, but, unlike super-formulas, which are sometimes wrong, more reliable.

You can work by selection the > a. For this, y is chosen so that the number on a not shared. For this, the number is simply multiplied by a natural number and the quantity is added (or, on the contrary, is subtracted) (for example, R), which is less a:

y = Ra + k

If, for example, a = 71, R = 3, q ​​= 10, then, respectively, the here it will be equal to 713. Another selection, with degrees, is also possible.

Compound numbers, unlike mutually simple ones, are divided into themselves, and to 1, and to other numbers (also without remainder).

In other words, natural numbers (except one) are divided into compound and simple numbers.

Simple numbers are natural numbers that do not havenontrivial (other than the number itself and one) divisors. Particularly important is their role in today's modern, rapidly developing cryptography, thanks to which the theory of numbers, previously considered a discipline of the most abstract, has become so in demand: data protection algorithms are constantly being improved.

The largest prime number founddoctor-ophthalmologist Martin Novak, who participated in the GIMPS project (distributive calculations), along with other enthusiasts, who numbered about 15 thousand. The calculations took six long years. It involved two and a half dozen computers located in the eye clinic of Nowak. The result of the titanic work and perseverance was the number 225964951-1, with the writing in 7816230-decimal places. By the way, the record of the largest number was placed six months before this opening. And the signs there were half a million less.

A genius who wants to name a number, wherethe duration of the decimal record will "jump" ten millionth mark, there is a chance to receive not only worldwide fame, but also 100 000 dollars. By the way, Nyan Hiratwal received a smaller amount ($ 50,000) for the number overcoming the millionth line of signs.