Generalization of the Brocard problem

Story

Hilbert in 1900 at the II International Congress of Mathematicians in Paris, noted the practical importance of the theory of numbers. The solution of abstract problems often led to the emergence of a new mathematical apparatus. A great example is the Great Fermat Theorem, during the proof of which, at the end of the 20th century, meromorphic functions were investigated that are used by modern design engineers at car factories and aircraft factories as well as by IT specialists in the framework of simulation modeling. The problems of "beautiful numbers" - simple twins and perfect numbers, which were considered practically useless in ancient Greece, now provide modern cryptography with robust algorithms for generating keys.

In 1913, Ramanujan popularized an undefined equation:

$$

$$n! + 1 = m ^ 2 (1)$$

Previously, it appeared in the works of Henri Brocard. According to historians, two mathematicians engaged in the study of this equation independently of each other. Obviously, the factorial grows faster than the square, so the first solutions can be quickly obtained by enumerating the values ​​of n. We get:

$$

$$4! = 5 ^ 2-1$$

$$

$$5! = 11 ^ 2-1$$

$$

$$7! = 71 ^ 2-1$$

In the year 2000, brute force values ​​were checked $$$n$before $$$10 ^ 9$and new solutions could not be found. The article proposes my approach to checking particular cases of the Brokar problem, and also formulates a generalized version of a mathematical problem, the solution of which will allow, regardless of the ABC hypothesis, to solve equations of the form:

$$

$$n! = P (x)$$

The necessary conditions

Modular arithmetic is a powerful tool for preliminary assessment of the complexity of the problem and the allocation of special cases. For example, it is easy to show that for even $$$m$Brokar's problem has no solution, since the factorial of any natural number, except one, is even. Prerequisite for a pair of values $$$(n, m)$in the Brocard equation, factorial is divisible by the expression:

$$

$$m ^ 2-1$$

Factorial, by definition, is the product of consecutive natural numbers. Using the properties of the natural series, one can determine the degree of a particular number in the canonical factorization of factorial. For example, $$$16!$contains 16 consecutive multipliers. Every second multiplier is divided by 2, every 4th - by 4, every 8th by 8, and every 16th by 16. Thus, the decomposition $$$16!$contains 2 to the power $$$1 + 2 + 4 + 8 = 15$. From here, if there is a pair $$$(16, m)$, which is a solution to the Brocard problem, $$$m ^ 2$must give the remainder of 1 when dividing by any power of two up to the 15th inclusive. We formulate the necessary condition for $$$m$when solving equation 1:

Let be $$$n!$does not exceed a certain degree $$$k$prime numbers $$$p$and there is a number $$$m$in which the pair $$$(n, m)$is a solution to equation 1. Then $$$m ^ 2-1$must be divided into all degrees $$$p$before $$$F (k)$where $$$F$- function of counting the degree $$$p$in decomposition $$$n!$. (2)

P-property

Let there is an algorithm A checking the necessary condition 2 for some prime number $$$p$. We call this algorithm the P-test. Let there also be a natural $$$n$satisfying the condition: $$$(n-1)! <m ^ 2 <n!$
Then we will say that the number $$$m$has a p-property.

Consider a 2-test process for an arbitrary $$$m$between $$$1023!$and $$$1024!$. For $$$m ^ 2$The following statements will be valid:

1. $$$m ^ 2$gives the remainder 1 when dividing into all powers of two to $$$2 ^ {1023-10 = 1013}$inclusive;
2. $$$m ^ 2-1$not divided by $$$2 ^ {1024-10 = 1014}$.

In practice, most square numbers between $$$1023!$and $$$1024!$fail 2 test in the first 200 iterations. If the number $$$m ^ 2$from the specified interval and $$$m$has a 2-property, then in binary numbering system $$$m ^ 2$ends in $$$100..001$where zeros are exactly 1012. Then, to check condition 2, you can calculate $$$m ^ 2$up to the last 8 digits and check the last 8 digits. If there is a sequence other than $$$0000 0001$then the 2 test fails. Consistently calculating each test value with an accuracy of 8, 16, 24, etc. characters can quickly check condition 2 for a large set of values, using a minimum of system resources. Chain sizes that are multiples of 8 are justified by the byte structure of the main memory of modern computers: a whole byte will be used to store smaller chains. For large chains that are not multiples of 8, there will also be unused memory bits.

Suppose you need to check the statement:
Among $$$n$from the segment $$$[k_1, k_2]$no solution to equation 1 for any $$$m$where $$$n, m, k_1, k_2$- natural.

Using the Stirling formula, we define the intervals $$$(a_1, b_1), (a_2, b_2), .., (a_l, b_l)$where $$$l = k_2-k_1 + 1$. For the i-th interval:

$$

$$a_i = {(s / e)} ^ s e ^ {1 / {12s + 1}} {\ sqrt {2 \ pi s}}$$

$$

$$b_i = {(s / e)} ^ s e ^ {1 / {12s}} {\ sqrt {2 \ pi s}}$$

$$

$$s = k_1 + i-1$$

Then the statement is true:
If among square numbers from $$$(a_1, b_1), (a_2, b_2), .., (a_l, b_l)$none passed the 2 test, then equation 1 has no solution on the segment $$$[k_1, k_2]$. The reverse is not true.

Generalization of the Brocard problem by the necessary condition

In general, a square number with a p-property has, in the calculus system with the base $$$p$view: $$$t00..001$with number of zeros $$$F (k) -1$. Then we can generalize the P-property problem:
Let two functions be described: $$$F$and $$$G$returning natural values ​​for any natural argument, and $$$G$not representable as a polynomial with integer coefficients. Then it is necessary to formulate a criterion in which among the numbers $$$m$lying between $$$G (t)$and $$$G (t + 1)$and having in the record in the calculus system with the base p type:

$$

$$k_100..00k_2 (3)$$

you can select only those that have a natural root of the nth degree, where the number of zeros in record 3 is given by the function $$$F$depending on $$$t$. Wherein, $$$k_1$can be a parameter, an arbitrary value or a constant, and $$$k_2$- always a constant. (four)

For example, you can set the problem of extractability of a cubic root from numbers $$$n$having the form in hexadecimal $$$k00..001$where $$$k$any hexadecimal number is greater than 1, and the number of zeros for a particular $$$n$equal to the greatest $$$t$For which the inequality holds:

$$

$$2 ^ t + 3t-1 <n$$

The basis for writing the article was a statement about the direct relationship between the number of zeros in record 3 in an arbitrary calculus system for the value of the left side of equation 1 when substituting the already found roots and the number $$$n$. If equation 1 has exactly 3 roots, this fact can be proved by solving the corresponding particular case of problem 4. The reverse is not true.

Conclusion

Speaking about the practical importance of abstract problems from number theory, as a factor stimulating the development of the mathematical apparatus, it is worth mentioning an interesting equation in integers, the solution of which is impossible within the framework of the above generalization:

$$

$$11 + ({2 ^ {n ^ 2-1} -2 ^ {3n-3}}) / (2 ^ {n-1} -1) \ equiv 0 \ pmod {2 ^ {m + 1} -1 } (5)$$

This equation follows logically from attempts to approximate Luke’s numbers by the non-recurrent method. Solving problem 5 will help discover new properties of Mersenne numbers and formulate the necessary conditions to speed up the work of distributed search for large prime numbers based on the Luke-Lemere test.

By analogy with the weak Goldbach problem, it is assumed that the P-tests will help to obtain a large lower bound for the whole roots of equation 1, other than $$$(4, 5), (5, 11)$and $$$(7, 71)$, and the study of Problem 3 will lead to the proof of the insolubility of equation 1 in integers for sufficiently large values ​​of n.

Sources

Gilbert's problems
Brocard's task