A deterministic method of factorization of numbers based on the use of mod 6 and mod 4

ABOUT! How many miraculous discoveries are prepared by the
enlightenment of the spirit,
And experience, the son of difficult mistakes,
And genius, friend of paradoxes,

And chance, god inventor ...
A.S. Pushkin

Instead of joining

I hope to present a solution to the problem of factorization of numbers, based on the use of mod 6 and mod 4, which allowed us to find the laws governing the translation of quadratic dependencies into linear ones.

Based on the found regularity, a technique was written that, according to the author, when writing a program, opens up the possibility of significantly reducing time costs when factoring numbers using non-probabilistic determinate methods of mathematics.

According to this technique, a program was written by a programmer - self-taught Belykh Sergey Alekseevich, which showed its effectiveness. Unfortunately, it is not adapted to large numbers. The technique is written as an algorithm for compiling a program, with explanations. The algorithm is presented in tabular form.
Based on the correlation between the coordinates of the numbers according to mode 6 and
mode 4, a correlation dependence is also provided between the numbers of numbers according to these modules: N6; N4.
Recall that all composite numbers are located in 4 quadrants, both when using the coordinate system according to mode 6, and when using the coordinate system according to mode 4.
Each table is compiled for four of 16 possible options. Why out of 16?
Each quadrant contains compound numbers, characterized by 4 design options.
Design options depend on the parity of coordinates, and on the ratio of coordinate values ​​of different parity.

For more explanations of the procedure, follow cat.



We turn to the table containing the numbers of the first number series, the numbers of which take the form: N = 6 * xy + x + y:

Table 1 (A)

y \ x	1	2	3	4
1	8	fifteen	22	29th
2	fifteen	22	41	54
3	22	41	54	79
4	29th	54	79	104

Thus, we can fill in any cells of the table. So, the number L ₁ , whose number N ₁ is in table 1 (A), can be represented as:

L ₁ = 6 (6xy + x + y) + 1,

where N ₁ = 6 xy + (x + y).

At the same time, both coordinates of the number of this table are positive, but can be either even or odd. We draw attention to this, since the evenness of the coordinates, as well as the sign in front of them, affects the algorithm for calculating the correlation dependencies between the coordinates of the coordinate system compiled in mod 6 and the coordinates of the coordinate system compiled in mod 4. And as a consequence, the calculation of the correlation dependencies between numbers of numbers calculated by these modules. This is the main signs that cause differences in the factorization of the considered options.

So, the table row numbers are the coordinates whose sign depends on the number of the table in question, as well as the column numbers. The difference between the numbers of adjacent numbers in lines is a constant. The difference between the increments in the rows as well. For tables compiled by mod 6, this value is 6. For tables compiled by mod 4, this value is 4.

If, when compiling table 1 (A), the values ​​of the first quantities for calculation: 1,2, 3,4, 5, 6 ..., when compiling a table for the numbers of the first auxiliary number series, the number of which is expressed as: N sub> 3 = 6xy-xy: -1, -2, -3, -4, -5, -6 ...

Table 3 (C)

y \ x	1	2	3	4
-1	4	9	14	19
-2	9	20	31	42
-3	14	31	48	65
-4	19	42	65	88

For the numbers of the second auxiliary series we get:

Table 2 (B)

y \ x	1	2	3	4
1	6	eleven	16	21
2	thirteen	24	35	46
3	20	37	54	71
4	27	fifty	73	96

Table 4 (D)

y \ x	1	2	3	4
-1	6	thirteen	20	27
-2	eleven	24	37	fifty
-3	16	35	54	73
-4	21	46	71	96

By analogy, the tables for the second numerical auxiliary series in mod 4 are also calculated.

We proceed to consider a specific example.

The numbers of the numbers calculated by the modules used can belong to the same quadrant with the coordinate system used, or to different quadrants. But at the same time they are always in strict correlation with each other.

Also in the strict correlation dependence is the product of coordinates, their sum, and their differences, calculated according to these modules.

Consider the regularities of the methodology as an example L = 10525. We determine to which auxiliary number series this number belongs. The condition that a number belongs to the first or second numerical auxiliary series is that it belongs to the (+1) residue class of this number in mod 6, or to (-1) the residue class in mod 6.

N ₆ = (10525-1) / 6 = 1754;

A number refers to the first auxiliary class of numbers, meaning it can belong to either the first (A) or third (C) tables.

The next step is to determine: what parity can the coordinates of the considered number have? Since the number number is even, in this version both coordinates can have the same parity. We assume that both coordinates are even. In this embodiment, the coefficient of conversion of the value (x + y) (correction value) calculated according to mod 6 to the value of the correction value calculated according to mod 4 is 3/2 (k ₆ ).
This coefficient is remembered for comparing the numerical series of correction values ​​calculated according to mod 6 and mod 4.
Based on the number of the number according to mod 6, the numerical series of correction values ​​calculated on mod 6 is calculated with an interval of 6. The first value of the number series is the residue class, to which the number of the considered number in mod 6 belongs:

1754: 6 = 292 * 6 + 2.

Based on the obtained balance, taking into account the sign, we compose a numerical series of correction values ​​in mod 6, with an interval of 6: Now we determine the number number from mod 4 (similar to determining the number number from mod 6): N ₄ = (10525-1) / 4 = 2631; Based on the number of the number in mod 4, we calculate the number series of correction values ​​in mod 4 with an interval of 4. The first value of the number series is the residue class, to which the number of the considered number belongs to mod 4: (When translating the correction value represented by the sum of the even coordinates , the correction value obtained as a result of the translation retains the sign in front of the correction value). 2631: 4 = 657 * 4 + 3.

2 8 14 20 26 32 38 44 … (1)










Based on the obtained balance, taking into account the sign, we compose a numerical series of correction values ​​for mod 4, with an interval of 4: Based on a correlation coefficient 1 / k ₆ , we translate the values ​​of the numerical series of correction values ​​calculated for mod 4 into correction values ​​for mod 6: Based on a comparison of the numerical series (1) and (2), we construct a numerical series of correction values ​​calculated according to mod 6 with an interval of 24:

3 7 11 15 19 23 27 31 35 39…



2 4,666 7,333 10 12,666 15,333 18 20,666 26 … (2)



2 26 50 74 98 …

Now, we have all the necessary data for constructing the numerical series of discriminants, based on the numerical series of correction values ​​calculated modulo, is already 24. And, if we guessed with the option, the considered number is not simple, use one of the values ​​of the obtained numerical series of correction values and the corresponding discriminant, necessarily, will ensure the determination of the integer coordinates of the considered number.

Indeed, on the basis of the number number and the specific correction value, we can determine the estimated product of coordinates further by the Vieta formula:

D = (x + y) ^ 2 / (2 ^ 2) -4 * xy;

As a result, we obtain: An analysis of patterns led to results, for the consideration of which we use the consideration of the data in Table 10-1.

-291 -119 341 1089 2125 3449 5061 6961


Consider the table data by looking at both the columns and rows, and the results in the cells.

The first, second and third columns contain the changed, step-by-step, corrective values ​​(a _i ) used for calculation according to a specific discriminant., For the first, second and third columns.

Correction for the first column is carried out step by step, starting from the first correction value by an amount equal to -4;

For the second column, the value of the adjustment step is increased by 24. By analogy, for the third column. The fourth, fifth and sixth columns are calculated by the formula:

D _i - [(a _i ) / 2] ² (B _i )

For each row under consideration.

The seventh column is the difference (P) between the two calculated, taking into account the adjustment of corrective values, neighboring values ​​on a particular line.

The eighth column is the quotient of dividing the first calculated corrected value of the Discriminant by the difference (P), on a particular line.
Moreover, the integer quotient obtained in the calculations allows one to determine both the correction value equal to the sum of the coordinates and the value of y corresponding to the considered number. In the given example, 2 -3 * 24 = - y; 2 - (-3 * 24) = 74 = (x + y).

Do not think that I will give answers to all questions. We agree that the current laws are the answer. Without additional calculations, the true answer is difficult. And for calculations, you need a program that allows you to make a change to answer questions

Table 10-1

y \ x	1	2	3	4	5	6	7	8
1	2	26	fifty	-292	-288	-284	4	-73
2	22	46	-292	-240	-188	52	52	-5.615
3	-6	18	42	-300	-200	-100	100	3
4	-10	14	38	-316	-168	-20	148	-2,135

Annotation to the methodology

Based on the use of auxiliary number series in mod 6 and in mod 4. from the natural series of numbers, compound numbers are separated and divided into 16 groups (options). By comparing the parallel calculations, it was possible to determine whether or not the considered number belongs to the proposed group of composite numbers (the proposed option).

When analyzing a number to determine whether it is simple or not, the maximum number of calculations is 4. The calculation option is discussed below. For each group of numbers, calculation algorithms are formulated that formalize the analysis of numbers. To find the factors of the considered number, an alternative method for solving the quadratic equation with two unknowns has been developed. The technique is based on the found regularity of the translation of quadratic dependencies into linear ones, which, according to the author, significantly reduces the calculation of time costs.

An alternative way to solve the quadratic equation is that, in contrast to the traditional method, where the solution is sought by selecting the discriminant, and sequentially extracting the square roots, in the proposed method, the solution is sought by the integer commensurability of the corrected discriminants (D _i ) and the difference between them (D _{(i + 1)} -D _i ), by finding the integer quotient when dividing the first value by the second.

This approach allows you to use, in the analysis in a significant number of calculations, initial, insignificant in value. For each of the calculation options, a program has been compiled that uses the capabilities of Excel tables. According to the author, the technique after writing the program will allow you to find new patterns in number theory, which should additionally affect the reduction of time costs when factoring numbers.

Question status (introduction to the methodology)

The problem of actually decomposing a given number into prime factors is one of the most difficult problems in mathematics. In the third century BC Erastofen proposed a method for finding all primes smaller than a given limit A. After some improvement at the beginning of the 20th century by Brun, this method is still the only way to solve this problem without using computing devices. Other attempts to find the laws of the distribution of primes have not yielded significant results.

The proposed work is a statement of the solution to this problem, based on the laws of distribution of composite numbers.
The work consists in searching for signs of the difference between primes and complex ones, and using these signs to determine whether the prime number is considered or not.
The solution to this problem has been reduced by us to the solution of a quadratic equation with 2 unknowns. Typically, such equations are solved by selecting one of the unknowns, in our case k, but this method, despite the fact that the calculation step has been increased to 24, is rather laborious for large numbers.

Method disadvantage

Difficulty and laboriousness without using software and PC.

Advantage of the method

The ability to use PCs and software, regardless of the number of characters in the number in question. In the present work, in our opinion, a good laboratory base has been created, suitable for solving various problems from the field of number theory, for example, expressing the cube of an integer as the sum of the terms of the first and second degrees. We know that when multiplying numbers with a significant number of digits through a group of PCs, the digits may disappear. The developed technique does not require the use of a PC group, since numbers with a small number of digits are used for calculations. The only continuous calculation that remains necessary is the division of a number.

Problems with writing a program according to the methodology under consideration led the author to the opinion that it would not be bad to try to explain in a more abbreviated form the principles inherent in the methodology. After all, this attempt, perhaps, will interest not only programmers, but also mathematicians who are not familiar with the regularity found.

Therefore, an attempt at such an exposition is based on the fact that consideration of one of the methodological options should provide an explanation of the whole work, and also, a regularity found that may not be useful to programmers either. When understanding the meaning of the work, all parts of the technique are comparable for understanding.

Purpose of writing a technique

The main objective of the proposed work is to determine whether a given number L is a prime, or if it is a product of at least 2 simple factors not equal to 1. In what follows, the word "number" always means an integer, non-negative, if not specified nasty. At the first stage, we applied the modulo comparison method. *

Any number L can be represented in the form:

L = m N + r,

where:
m is the given module;
N - we called the number number;
r is the remainder (can be positive, negative and equal to 0), r is in the range from - (m - 1) to (m - 1) (For m = 6 from - 5 to + 5).

We choose m = 6. This gives us the opportunity to exclude from an infinite number of numbers that are subject to our analysis, the numbers in which the factors 2, 3 and 6 are present, since the presence of these factors in the number is easily recognizable. All numbers to be analyzed are referred to by us as hard to recognize.

Regarding module 6, all natural numbers are distributed into 6 classes, depending on the remainder:

1) r = 0. L = 6 N (that is, all numbers in this class make up the module M itself)
2) r = 1; L = 6 N + 1, which is equivalent to r = -5; L = 6N - 5.
3) r = 2; L = 6 N + 2, which is equivalent to r = -4; L = 6N - 4.
4) r = 3; L = 6 N + 3, which is equivalent to r = -3; L = 6N - 3.
5) r = 4; L = 6 N + 4, which is equivalent to r = -2; L = 6N - 2.
6) r = 5; L = 6 N + 5, which is equivalent to r = -1; L = 6N - 1.
- * A module M is a system of all numbers that are multiples of a given number m. The number m is the smallest number of a given module M. If the numbers a and b, when divided by m, give identical residues, then they are called comparable modulo m. This is written as:

a Ξ b. (Mod m)

This relationship between a and b is called a comparison modulo m. Any number is comparable modulo m with its remainder from dividing this number by m. For example: if a when divided by m gives the remainder 1, then:

a Ξ 1; (mod m)

if it is necessary to add 1 to a so that the sum is divisible by m, then

a Ξ -1; (mod m)

In this case, –1 is called the “negative remainder”. The numbers of two classes are of interest to us:

L (+1) = 6N + 1; L (+1) Ξ 1 (mod 6) [1],

we called them branch numbers (+1); and

L (-1) = 6N - 1; L (-1) Ξ -1 (mod 6) [2] ,.

we called them branch numbers (- 1).

These numbers are odd; they are not divisible by either 3 or 6; that is, these are hard to recognize numbers. By analogy, the number is also considered when using mod 4.

Compilation of tables, including numbers of all difficult numbers of the 1st auxiliary number series

To systematize all the difficult numbers of the natural number series, 4 tables have been compiled. For compactness, we do not enter the numbers L themselves in the tables, but their numbers N. If necessary, knowing N, we can calculate L. by the formulas [1], [2]. And vice versa: by a given L we can calculate its number N. All the tables are compiled according to the principle of the Pythagorean tables.

Consider the characteristics common to all tables. In the zero row of each table we number the columns: 1, 2, 3, 4, ... In the column of each table we number the rows: 1, 2, 3, 4 ...

Sample table:

y \ x	1	2	3	4		y i
1	x
2		x
3			x
4				x
...					x
x i						N i

The zero row and column of each table will be taken as the coordinate axis, denoting them y and x. This statement is based on the fact that all composite numbers are located in four tables (quadrants of a given coordinate system). The row and column numbers located on the coordinate axes are the coordinates of the numbers of the considered number series with the corresponding sign (the coordinates of the numbers N are also the coordinates of the numbers L).

Take in any cell of the table the number N _{i of the} number L _i . The coordinates of the number N _i (and the number L _i ) are x _i , y _i . The number L _i is the product of X _i and Y _i. We write this in a formalized form:

L _i = X _i Y _i , where X _i = 6 x _i ± 1; For _i = 6, for _i ± 1 [3]
L _i = 6 N _i ± 1.

N _i i is listed in the table (see sample table).

* cells for which x = y are selected in the table. These cells make up the main descending diagonal of each table. It originates from x = y = 1 and lasts indefinitely.