Every student knows that all numbers are divided into simple and compound. Moreover, those who study mathematics diligently know their properties. However, if the answer to the question of how many divisors a prime number is hidden in the very definition of this concept, then figuring out the number of simple divisors for a given one is a rather difficult task. It is solved using the enumeration method and probabilistic algorithms implemented on a computer.
A bit of history
It is reliably known that the ancient Greeks were the first to engage in a serious study of the properties of primes. However, their existence was known several millennia before Aristotle included the theorems on their properties in his famous “Beginnings”. The ancient Greeks came up with the sieve of Eratosthenes, which is an algorithm for finding primes from the interval [1, n].
In the 17th century, a breakthrough in their study was made by Pierre Fermat and Maren Mersenne. The first one formulated a theorem, later named after him, according to which all numbers of the form 2 2n are prime, proving it for n = 1..4. However, later Leonard Euler showed that for n = 5 a composite number is obtained. In parallel, Maren Mersenne singled out primes of the form 2 p - 1, in which p is a prime. They are interesting in that it is easy for them to verify compliance with the simplicity criterion. Given this fact, Mersenne numbers are used to identify super-large primes. At the moment, the limit of the known looks like 2 77232917 - 1.
In addition, they are widely used in the creation of random number generators, which are widely used in practice.
Legendre and Gauss also played a large role in the study of prime numbers. These scientists hypothesized their density.
Sieve of Eratosthenes
If you can immediately call the prime divisors of the number 4, then for large numbers it is usually quite difficult to do this. People began to think about solving this problem several millennia ago. In particular, the ancient Greek mathematician Eratosthenes, who lived at the junction of the third and second centuries before Christ, came up with an algorithm for finding all primes smaller than the integer n.
It is called the sieve, as it "sifts" or in a modern way "filters" all numbers except simple ones.
The algorithm consists of the following commands:
- write out all integers from 2 to n;
- set the variable p to 2 because it is the smallest prime number;
- cross out in the list all numbers from 2p to n multiples of p;
- assign the value of the variable p to the value of the first, not crossed out number of the recorded sequence, which is greater than p;
- repeat 3rd and 4th while possible.
If everything is done correctly, then in the list all prime numbers from two to n will be crossed out.
To implement the sieve of Eratosthenes on an electronic computer, a modernized algorithm is used. At the 3rd step, it is possible to cross out numbers, starting from the number p 2 , since all composite numbers that are less than it will be crossed out by this time. Then the stop of the algorithm should occur when the condition p 2 > n is fulfilled.
It should also be taken into account that all primes, with the exception of two, are odd, therefore, starting from p2, you can “filter” by 2p.
The main theorem of arithmetic
By definition, a prime number has two divisors. One of them is 1, and the second is this value itself.
Before finding out what is the number of prime divisors of a number, it is worthwhile to devote some time to studying the basic theorem of arithmetic. According to it, a positive integer n> 1 can be represented as n = p 1 * ... ⋅ * p k , where p 1 , ..., p m are primes. Moreover, such a representation is unique up to the order of its factors.
The corollary of this theorem can be formulated as follows: any natural number n can be represented in the form n = p 1 d1 * p 2 d2 * ... * p k d m (in another formulation: the canonical decomposition of n into simple factors has the form n = p 1 d1 * p 2 d2 * ⋅ ... ⋅ * p k d m ), where p 1 <p 2 <... <p m are primes, and d 1 , ..., d m are some positive integers.
In addition, the basic arithmetic theorem already known to you can be rephrased as follows: any canonical decomposition of n can be considered identical if we do not pay attention to the order of the divisors. This means that in practice, for a significant part of the numbers, there are many fairly simple algorithms for decomposing them into prime factors, which ultimately give the same result.
Simplicity criterion
Before figuring out how to find the largest prime number divisor (NAP) n, you need to look into another important issue.
So, let's find out by what algorithm it is possible to establish whether a quantity has other divisors other than unity and itself.
This can be done by sorting through the primes p 1 , ... p k . Moreover, it is possible to complete the cycle as soon as p i + 1 , for which the check was performed, will satisfy the condition (pi +1 ) 2 > n.
Let us explain why the search can be limited by p i > = sqr (n).
Suppose the number n, investigated for simplicity, has some divisor p. Then d = n / p will also be its divisor. But, since d and p are different numbers, none of them can be greater than the root of n.
How to find the largest prime divisor of n
You can find nap n, acting according to the following scheme:
- Divide n into two if it is even or by three if it is odd. The exception is n, the last digit in the decimal notation of which is zero or five. This number can immediately be divided into five.
- If the result is not an integer, then divide n into the next integers, sorting them down to p i > = sqr (n).
All actions are performed on the resulting number n 1 in the same order as presented above, only with the condition p i > = sqr (n 1 ).
If, at any of the search steps, n 1 is not divisible by one of the prime numbers, then n is an integer and is its own NPD. Otherwise, we obtain n 2 and continue the division with enumeration until the moment when at the (i + 1) step we establish that n i is an integer.
Example
Find the prime divisors of 276.
- divide by "two";
- we get 138;
- since the number is even, we again divide by "two";
- the result is 69;
- divide by the next prime number “three”;
- we get 23.
Since this number is prime, we can summarize. Simple dividers 276 are 2, 3, and 23.
How to find the number of prime divisors of a number
If we are talking about a whole small number, then solving this problem is not difficult. Consider a specific example. Find the prime divisors of 54.
For this:
- 54 divided by "two" and get 27;
- 27 is odd, therefore we will divide it no longer into "two", but into the next prime number, that is, "three";
- note that 27 = 3 3 ;
- thus, decomposition 54 has the form 54 = 2 1 * 3 3 , i.e. the prime divisors of 54 are two and three.
However, this is not all we wanted to know. Now we find the number of prime divisors of 54. It is equal to the product of the powers of the prime factors of the canonical expansion of the number n = p 1 * d1 p 2 d2 * ⋅ ... ⋅ * p m d m increased by 1. In other words, in the general case K = (d 1 +1) * ... * (d m +1).
Then for 54 we have K = 2 * 4 = 8, i.e., the total number of divisors is eight.
Please note that everything was greatly simplified if we were talking about 23, 37, 103, etc., since everyone knows how many divisors a prime number has.
Example
Find the number of prime divisors of 9990.
- since the number 9990 ends with the number "zero", it is divided into five and two.
- we have 999.
- as a result of division by three, we have 333;
- again divided by three, we get 111;
- divided by three, we have 37;
- 37 is a prime number, since it is not divisible without remainder by any of the prime numbers that are between the two and the root of the number 37;
- we count the number of prime divisors of 9990. These are 2,3,5 and 37, that is, there are four of them in total.
The problem of large numbers
Oddly enough, the task of finding all the prime factors of a number is quite complicated. The fact is that so far we have considered only numbers whose decimal notation consisted of one to four digits. For them, all calculations are performed in several steps and can be easily mastered with only a pen and a sheet of paper on hand. The situation is different when it comes to, for example, a 1000-digit number. It will take more than a billion years to find all its prime factors, even if the world's most powerful supercomputer is involved.
Prime numbers and information security
Every modern person who takes advantage of the opportunities that have arisen due to the emergence of local computer networks and the Internet needs to protect the confidentiality of their personal data, electronic correspondence, etc. For this purpose, public-key cryptographic algorithms are used.
On systems with dozens and hundreds of users, key management is a serious problem. To prevent the attacker from mastering key information, it is necessary to introduce some random variable into the encryption process.
For this purpose, the most common RSA algorithms currently use large primes.
There are a total of 10151 primes 1 to 512 bits long, inclusive. At the same time, for numbers that are close to n, the probability of the fact that a randomly chosen number is prime is 1 / ln n. Thus, the total number of primes that are less than n is n / ln n. This suggests that it is highly unlikely that 2 people will choose the same large prime number.
Miller test - Rabin
For cryptographic purposes, this type of definition of simplicity of a number is often used, which has several modifications.
The Miller – Rabin test is based on checking a number of conditions that are satisfied for numbers that are divisible only by 1 and by themselves. If at least one of the requirements is violated, this “test” number is recognized as composite.
For a given m, odd integers t and s are found such that the condition m-1 = 2 s t is satisfied.
Then a random number a is chosen such that 1 <a <m. If a does not indicate the simplicity of the number m, then the program should give the answer “m composite” and complete its work. Otherwise, another random number a is selected and the test is repeated again. After r witnesses of simplicity are established, the answer “m, probably, simple” should be given, and the algorithm will finish its work.
A corollary of Rabin’s theorem is the fact that if r numbers that are randomly selected are recognized by witnesses to determine the simplicity of m, then the probability that it is composite cannot exceed (4 -r ).
Now you know how many divisors a prime number is and how to figure out the most primitive algorithm for computing NAPs. This knowledge will help you in solving many practical problems.