Factorization/Integer/Deduction
The following study or essay is by SHAWWPG19410425. It incorporates Original research. See page history for dates of contributions. There has been editing of this page also, by Abd, not intended to change (or validate) the meaning, but only to assist with formatting.
A deductive solution to the factorization of uneven integers
editPrime factorization will be seen to be properly a problem of logic and Diophantine Equations.
Diophantine solutions necessarily exist, because of the Equation below, where it is proved that every uneven integer having two prime factors is expressible as the difference of the squares of two integers, M^{2} - K^{2}. The factors of this difference of squares are the prime factors. However, the Equation is universally valid for any combination of primes and uneven composite factors.
Using logical deduction, the solutions for M and K can be found by solving an optimal Diophantine equation and then in the proper order reading off the coefficients of the variables to degree unity in this equation which are seen in the examples done so far to relate directly to the values of M and K. The coefficients in some cases are the actual values of M and K, but this seems to depend on the congruencies of M and K. Otherwise reversing a series of substitutions returns to same results, the values of M and K.
In Example 3 of the deductive solution (below), a six digit decimal number has been factorized using just one standard division by four followed by about nine successive divisions by two. There were about as many elementary substitutions as there were divisions. Classical factorization that uses the square root of the integer to be factorized would have needed one hundred and forty-eight long and shorter prime decimal divisions to accomplish the same result. The deductive solution is more intricate than the classical solution.
In the following, every variable label or numeral is without exception an integer.
NOTATION USED: The period [full stop] indicates multiplication, but this could be omitted. Where numbers are being multiplied, x is used to avoid confusion with a decimal point. The upper case sign ^ indicates exponentiation using curly brackets {} to enclose the exponent. Subscripts are indicated by square brackets [ ]. Square brackets have been used to the minimum, but sufficient to avoid ambiguity. Division by the forward sloping bar /. Round brackets () to be introduced to make the equations more readable.
There are four classes of classes of composites. The evenness [e] or unevenness [u] of M and K are indicated for each class of classes. Given q[1] and q[2], the integer q[2] exceeds q[1] and the integers q[1] and q[2] are represented as: [4.h[j] + H], where subscript [j] is one or two and the integer, H is one or three. The four classes of classes of composites are of the form:
Class of Classes [I] [4.h[1] + 1] x [4.h[2] + 1] giving a composite, Q:
[16.h[1].h[2] + 4.[h[1] + h[2]]] + 1 and M[u], K[e]
Class of Classes [II] [4.h[1] + 1] x [4.h[2] + 3] giving a composite, Q:
[16.h[1].h[2] + 4.[3.h[1] + h[2]]] + 3 and M[e], K[u]
Class of Classes [III] [4.h[1] + 3] x [4.h[2] + 1] giving a composite, Q:
[16.h[1].h[2] + 4.[h[1] + 3.h[2]]] + 3 and M[e], K[u]
Class of Classes [IV] [4.h[1] + 3] x [4.h[2] + 3] giving a composite, Q:
[16.h[1].h[2] + 4.[3.h[1] + 3.h[2]] + 8] + 1 and M[u], K[e]
The first few members of the class of classes [I] are:
[[[5, 9], [5, 13], ... ]], [[9, 13], [9, 17], ... ]], [[13, 17], [13, 21], ... ]]] to infinity.
With five the smallest of the set of [4.h + 1] integers and three the smallest of the set of [4.h + 3] integers, the first few members of class of classes [II] are:
[[[5, 7], [5, 11], [5, 15], ... ]], [[9, 7], [9, 11], [9, 15], ... ], [[13, 7], [13, 11], [13, 15] ... ]]] to infinity et cetera.
Representative examples respectively from the four major classes to solve are: [1] Q[6] = 65 [5, 13], [2] Q[8] = 323 [17, 19], [3] Q[8] = 319 [11, 29], [4] Q[9] = 713 [23, 31]
Equation 1 below is central to the deductive factorization solution and expresses every uneven integer, Q[N] that has two prime factors as the difference of two perfect squares.
Equation 1 is found to be universally true for every uneven composite that is derived from uneven composite factors.
Equation 1 is true for even numbers where a congruency one or three modulo four is not involved.
Example q[1] = 21 and q[2] = 35. This gives Q[9} = 735 with M = 28 and K = 7.
Uneven numbers can be classified into two categories: [a] 4.k + 1 [b] 4.k + 3.
Conventionally, the prime numbers are listed: [2, 3, 5, 7, 11, 13, 17, ... ]. This does not look very logical, for two [2] is really in a class of its own, containing just one member, itself, and perhaps it would be better then to place two in a different class from the other primes.
The interval between successive uneven integers is two. Given that q[2] is greater than q[1], the interval between q[1] and q[2] can be written as:
[q[2] - q[1]] = 2.K
That is: [q[2]^{2} - q[1].q[2]] = 2.K.q[2]
Substituting Q = q[1].q[2], we have:
[q[2]]^{2} - Q] = 2.K.q[2]
Equation 1 is a quadratic in q[2].
Relabeling q[2] as x, the quadratic is:
x^{2} - 2.K.x - Q = 0
The solutions are:
x[1] = K - [K^{2} + Q]^{1/2} and
x[2] = K + [K^{2} + Q]^{1/2}
The product of the two roots are: [a]
x[1].x[2] = - Q
[b] K^{2} - [K^{2} + Q]
These are equal, giving:
- Q = K^{2} - [K^{2} + Q]
The simplified discriminant, D is:
D = K^{2} + Q
Since q[2] is an integer, the discriminant has to be a perfect square, say M^{2}.
That is: K^{2} + Q = M^{2}
From the products of the roots,
Equation
edit- Q = K^[2] - M^{2} or Q = M^{2} - K^{2}
We find that x[1].x[2] = - q[1].q[2]
Since K and M are integers, x[1] and x[2] are integers. By the fundamental theorem of arithmetic, the prime factors are unique. Therefore the prime factors are the roots of the above quadratic equation. This constitutes a very elementary proof that apart from the algebraic sign, q[1] and q[2], the prime factors of Q are given by the roots of the quadratic equation, as below.
q[1] = [M - K] and q[2] = [M + K]
Example: q[1] = 3, q[2] = 7. Solving the simultaneous equations:
M + K = 7 and M - K = 3, we find M = 5 and K = 2.
In the Equation either [a] M^{2} is uneven and K^{2} is even or alternatively [b] M^{2} is even and K^{2} is uneven.
Two major cases.
[a] It is found that if Q is of the form [4.j + 1], then M is uneven and K is even.
The perfect uneven square, M^{2} can be written in two ways:
[i] M^{2} = [4.h + 1].[4.h + 1]
- = [16.h^{2} + 8.h + 1]
or
[ii] M^{2} = [4.h + 3].[4.h + 3]
- = [16.h^{2} + 24.h + 9]
The perfect square, K^{2} can be written in two ways as:
[i] K^{2} = [2^{L}.[4.k + 1]].[2^{L}.[4.k + 1]]
- = 2^{2.L}.[16.k^{2} + 8.k + 1]
or
[ii] K^{2} = [2^{L}.[4.k + 3]].[2^{L}.[4.k + 3]]
- = 2^{2.L}.[[16.k^{2} + 24.k + 8] + 1]
[b] If Q is of form [4.k + 3], then M is even and K is uneven. The different representations of M and K are similar to the above. However in case [a] and only some of the representations may be valid, this depending on the structure of Q. Case [b] deferred.
Using equation 1 and the fact that Q is either a [4.k + 1] or a [4.k + 3] number, a Diophantine equation results from #Equation 1 and the fact that Q[N] is either a [4.k + 1] or a [4.k + 3] number.
In the Equation, there are two unknowns in one equation and immediate elementary algebraic solutions for the prime factors through deductive logic.
Deductive solution
editThis uses the elementary logic of arithmetic leading to a Diophantine equation that has two immediately obvious solutions. Then the series of substitutions are reversed giving the integers, M and K. The index, L is found early in the process. In the examples, this Diophantine equation has been found to contain the unknowns M and K as the numerical coefficients of the unknowns of degree unity in this Diophantine equation.
Some logic: given that U and u are uneven class integers and E and e are even class integers and k is a positive integer, then: U = e + u, E = u + u, E = e + e, E = e and U = u are logically true, but U = e and E = u are logically false or contradictory. The logical multiplication rules are: E = e.e, E = e.u, U = u.u and are all logically true. The equation: 2^{k}.u = E is logically true provided that k is equal to, or greater than unity. If k = 0 or negative, then this equation is logically false [a logical contradiction].
Example 1
editFactorize Q = 65 [5, 13] [M = 9, K = 4, X[1] = 9 and X[2] = 1
[Note that the period of the uneven integer has no relevance in this solution]
An essential part of solving for the terms in the difference of two squares is to know the congruencies of the terms in the difference of two squares in advance. There is a strategy for doing this that may be successful but has to be developed on logical lines first.
It has been found that where Q has the form: [4.k + 1], then M is uneven and K is even.
M takes the form: [4.m + 1] or 4.m + 3] and K takes the form: 2^{L}.[4.z + 1] or 2^{L}.[4.z + 3] There are four selections for the form of M and the form of K combined as below to represent Q. The actual selection would depend on Q, otherwise in the absence of such knowledge, there would be four tries and three errors.
In this example, M = [4.m + 1] and K = 2^{L}.[4.z + 1]. The integer, Q takes the form:
M^{2} - K^{2} = [4.m + 1]^{2} - 2^{2.L}.[4.z + 1]^{2}
The above is one of the four selections.
The factors in this example are given by:
M - K = [4.m + 1] - 2^{L}.[4.z + 1]
and:
M + K = [4.m + 1] + 2^{L}.[4.z + 1]
Substituting for the numerical value of Q,
65 = [16.m^{2} + 8.m + 1] - 2^{2.L}.[16.z^{2} + 8.z + 1]
Obviously:
64 = 16.m^{2} + 8.m - 2^{2.L}.[16.z^{2} + 8.z + 1]
This equation can always be divided by four, ultimately because K is even and the minimum value of L is unity. Therefore:
16 = 4m^{2} + 2.m - 2^{2.L - 2}.[16.z^{2} + 8.z + 1]
In general the index, that is the exponent of two, after division by two, takes the form either [2.L - [2.J - 1]] or [2.L - 2.J] Only in the latter case could the exponent have the value, zero. Suppose that: [2.L - 2] = 0, making L = 1. In this case, there is an even number on the left side of the above equation and four definitively even numbers on the right side and uneven unity. The equation would therefore be inconsistent and consequently: [2.L - 2] is an even positive integer.
Division of the above equation by two gives:
8 = 2.m^{2} + m - 2^{2.L - 3}.[16.z^{2} + 8.z + 1]
The index: [2.L - 3] cannot be zero, but is some uneven exponent of two because we are only considering integers, so that 2^{2.L - 3} is not unity, but some power of two.
It follows that m is even, say m = 2.h. Substitution for m gives:
8 = 2.[2.h]^{2} + 2.h - 2^{2.L - 3}.[16.z^{2}+ 8.z + 1]
This becomes:
8 = 8.h^[2} + 2.h - 2^{2.L - 3}.[16.z^{2} + 8.z + 1]
Division by two gives:
4 = 4.h^{2} + h - 2^{2.L - 2.J}.[16.z^{2} + 8.z + 1]
In the expression: [2.L - 2.J], the first encountered value of J that could satisfy the above equation has been found to be the proper value of J. The value: J = 1 was not valid, however the next value, J = 2 could be valid and therefore is valid. This latter statement was found to be true.
If J had been taken to be three, such that: [2.L - 6] = 0, this would lead to a logical contradiction because: [2.L - 6] = - 2. Multiplying through by four to clear the fraction: 1/2^{2} would leave several additive terms all even and the unity on the extreme right. This would mean that an even integer is being equated to an uneven integer which is a logical contradiction. Otherwise, taking L = 3 leads to an indefinite nonterminating series of equations.
The index, L = 2 and the equation becomes:
4 = 4.h^{2} + h - 16.z^{2} - 8.z - 1
In this equation, the left side is even but the right side contains unity, an uneven integer. So that this equation can be logically true, the unknown h has to be written: h = 2.Y + 1.
Substitution brings:
4 = 4.[2.Y + 1]^{2} + [2.Y + 1] - 16.z^{2} - 8.z - 1
Simplifying in stages [to avoid mistakes]:
4 = 4.[4.Y^{2} + 4.Y + 1] + [2.Y + 1] - 16.z^{2} - 8.z - 1
This becomes:
4 = 16.Y^{2} + 16.Y + 4 + 2.Y + 1 - 16.z^{2} - 8.z - 1
This is:
0 = 16.Y^{2} + 18.Y - 16.z^{2} - 8.z
This is exactly the type of equation required so as to be able to solve for the values of M and K. Dividing by two:
0 = 8.Y^{2} + 9.Y - 8.z^{2} - 4.z
The immediately obvious solutions to this Diophantine equation are: Y = 0 and z = 0 This gives h = 1 and therefore m = 2 giving M = 9 and K = 4
Note the respective coefficients of Y and z. However, the above equation is not optimally Diophantine [a matter almost not noticed]. To reduce this equation to optimality, a few substitutions are required. Substitute Y = 2.w. this equation becomes:
0 = 32.w^{2} + 18.w - 8.z^{2} - 4.z
Division by two gives:
0 = 16.w^{2} + 9.w - 4.z^{2} - 2.z
Substitution: w = 2.u This gives:
0 = 64.u^{2} + 18.u - 4.z^{2} - 2.z
Division by two gives:
0 = 32.u^{2} + 9.u - 2.z^{2} - 1.z [the optimal Diophantine equation]
The coefficient of u is seen to be X[1] and the coefficient of z is seen to be X[2]. The terms in the difference of two squares, X[1] was nine and X[2] was unity.SHAWWPG19410425 (discuss • contribs) 20:48, 21 March 2014 (UTC)
Example 2
editfactorize Q = 2701 [37, 73]
Solution: Q is of the form: [4.k + 1]. We solve for M and K, where K = 2^{L}.Z
M is of the form: [4.m + 3] and K is of the form: 2^{L}.[4.z + 1] This much is known because we can in this case find M, K and Z from: q[1] = M - K and q[2] = M + K, the prime factors. We find that: M = 55 and K = 18. That is L = 1 and Z = 9
If the form of M and Z was not known, then one way would be to tabulate for L = 1, and fixed Z say, values of M for each of the four combinations of forms [congruencies] of M and Z against the ordinal of the resulting Q, this ordinal being: n = [Q + 1]/2. The ordinals would form a different sequence in each of the four cases. The sequence to which a particular Q belonged would identify the appropriate form of the M and Z associated with that Q.
Otherwise, the M and Z could be tabulated for a succession of values of Q in numerical order where prime or composite factors existed with the congruencies of M and Z, index, L and the ordinal of Q.
The minimum value of L is unity where exclusively either M or K is even as the case may be.
Writing Q in the explicit form:
[M^{2} - K^{2}] = [M^{2} - 2^{2.L}.Z^{2}]
= [4.m + 3].[4.m + 3] - 2^{2.L}.[4.z + 1].[4.z + 1]
Substituting for the actual value of Q and simplifying, we get:
2701 = [16.m^{2} + 24.m + 9] - 2^{2.L}.[16.z^{2} + 8.z + 1]
Subtracting unity from left and right:
2700 = [16.m^{2} + 24.m + 8] - 2^{2.L}.[16.z^{2} + 8.z + 1]
As in the previous example, we can divide each side by four, without producing any fractions.
675 = 4.m^{2} + 6.m + 2 - 2^{2.L - 2}.[16.z^{2} + 8.z + 1]
The conclusion is that: 2^{2.L - 2} = 1 and therefore L = 1. otherwise, if 2^{2.L - 2} were even, then then the left side being 675, an odd number would be equated to the right side which would be an even summation of terms.
Rewriting the above equation:
675 = [4.m^{2} + 6.m + 2] - [16.z^{2} + 8.z + 1]
674 = [4.m^{2} + 6.m] - [16.z^{2} + 8.z]
Dividing each side of this equation by two gives us:
337 = 2.m^{2} + 3.m - 16.z^{2} - 8.z
The conclusion is that [m] is an uneven number. This is to make the right side of this equation an uneven summation. If [m] had been an even number, then we would have had an even summation on the right equated to 337, an uneven integer on the left.
Let m = [2.h + 1] (no subscript on h)
Substitution for m gives:
337 = 2.[4.h^{2} + 4.h + 1] + 3.[2.h + 1] - 8.z^{2} - 4.z
Simplifying, this becomes:
337 = 8.h^{2} + 8.h + 2 + 6.h + 3 - 8.z^{2} - 4.z or
332 = 8.h^{2} + 14.h - 8.z^{2} - 4.z
Dividing by two gives:
166 = 4.h^{2} + 7.h - 4.z^{2} - 2.z
The conclusion is that h is an even integer because the right side has to be an even summation.
Let h = 2.j Substitution for h into the above equation gives:
166 = 4.[2.j}^{2} + 7.[2.j] - 4.z^{2} - 2.z which is:
166 = 16.j^{2} + 14.j - 4.z^{2} - 2.z
Dividing this by two:
83 = 8.j^{2} + 7.j - 2.z^{2} - 1.z
There is a crisis [decision] here. Either [1] j is even and z is uneven, or exclusively [2] j is uneven and z is even. [By considerations similar to above] Given that f and g are integers,
Decision [1] Let j = 2.f and z = 2.g + 1 or exclusively [2] Let j = 2.f + 1 and z = 2.g
It transpires that decision [1] is wrong or false and decision [2] is right or true. How can it be known which decision is correct? The answer to this question will be seen.
Taking the true option [2] first, we have by substitution:
83 = 8.[4.f^{2} + 4.f + 1] + 7.[2.f + 1] - 2.[2.g]^{2} - 1.[2.g]
This becomes:
83 = 32.f^{2} + 32.f + 8 + 14.f + 7 - 8.g^{2} - 2.g
This becomes:
68 = 32.f^{2} + 46.f - 8.g^{2} - 2.g
Dividing by two gives:
34 = 16.f^{2} + 23.f - 4.g^{2} - g
This equation has the very same form as the equation [see below] resulting from the false option [1], except that the left side is even.
This means that the variables, f and g have either each to be uneven or alternatively, each have to be even. In each of these cases, the correct answer is found.
[a] Let f = 2.X + 1 and g = 2.Y + 1
Substitution gives:
34 = 64.X^{2} + 110.X + 34 - 16.Y^{2} - 18.Y
Cancelling the thirty-four gives:
0 = 64.X^{2} + 110.X - 16.Y^{2} - 18.Y
Dividing by two for good measure:
0 = 32.X^{2} + 55.X - 8.Y{2} - 9.Y
It is interesting to notice that the coefficients of X and Y respectively are M and Z, but this might just be a coincidence.
This is a Diophantine equation evidently having the solutions, X = 0 and Y = 0.
Reversing the substitutions presents the solutions for M and K.
Thus f = 1 and g = 1. j = 2.f + 1 and z = 2.g gives us: j = 3 and z = 2. Then h = 2.j gives h = 6. Integer, m = 2.h + 1 so that m = 13. M = [4.m + 3], so that M = 55. Index L = 1 from above and therefore K = 2^{L}.[4.z + 1], giving K = 18. The prime factors of 2701 are then [55 - 18] and [55 + 18] or q[1] = 37 and q[2] = 73.
[b] Let f = 2.W and g = 2.Z. Substituting into the above equation:
34 = 16.f^{2} + 23.f - 4.g^{2} - g gives:
34 = 16.[2.W]^{2} + 23.[2.W] - 4.[2.Z]^{2} - [2.Z]
This becomes:
34 = 64.W^{2} + 46.W - 16.Z^{2} - 2.Z
Dividing this equation by two gives:
17 = 32.W^{2} + 23.W - 8.Z^{2} - Z
This equation has the solutions, W = 1/2 and Z = 1/2 . The above equation can be made Diophantine by the substitution: X = 2.W and Y = 2.Z. That is W = X/2 and Z = Y/2 The equation then becomes:
17 = 32.[X/2]^{2} + 23.[X/2] - 8.[Y/2]^{2} - [Y/2]
Multiplying through by four gives:
68 = 32.X^{2} + 46.X - 8.Y^{2} - 2.Y
This equation is now Diophantine and has solutions X = 1 and Y = 1. reversing all of the substitutions returns the correct values for m and z in the above equation having the integer, Q, 2701 on the left side.
The result for M and K is the same for in this latter case, f = 1 and g = 1 as above.
Choosing the false option or incorrect option [1]. In this case, j = 2.f and z = 2.g + 1
Substitution into the above equation: 83 = 8.j^{2} + 7.j - 2.z^{2} - z gives:
83 = 8.[2.f]^{2} + 7.[2.f] - 2.[2.g+ 1].[2.g + 1] - [2.g + 1]
This becomes:
83 = 32.f^{2} + 14.f - 2.[4.g^{2} + 4.g + 1] - 2.g - 1
That is:
86 = 32.f^{2} + 14.f - 8.g^{2} - 10.g
Dividing by two gives:
43 = 16.f^{2} + 7.f - 4.g^[2} - 5.g
In this equation, either [a] f is even and g is uneven, or exclusively [b] f is uneven and g is even. This makes the equation logically true. However, if each of these options, [a] or [b] is used, then another equation of identical logical form to the above is reproduced. This situation recurs indefinitely.
What is found is that if in this equation, the left side is uneven, then the false option has been chosen. The false option leads to an indefinite unending series of intractable equations.
Example 3
editFactorize Q = 742529 [733, 1013] [M = 873, K = 140, L[2]/L = 2, Z = 35 The integer K can be written as 2^{2}.35] Except for the congruencies of X[1]/Y and X[2]/Z, no knowledge of M and K is assumed in advance [Y and Z are just convenient labels for X[1] and X[2] respectively] If a crisis arises in this example, the same procedure could be used as in Example [2].
Solution: the congruencies of 742529, 873 and 35 are respectively: unity, unity, three. Only the latter two congruencies are essential for the solution, the first being irrelevant here.
Q = [4.m + 1]^{2} - 2^{2.L}.[4.z + 3]^{2}
[difference of two squares, taking congruencies into account]
The starting equation is:
742529 = [16.m^{2} + 8.m + 1] - 2^{2.L}.[16.z^{2} + 24.z + 9] [using label m in place of y]
742528 = 16.m^{2} + 8.m - 2^{2.L}.[16.z^{2} + 24.z + 9]
We can divide the equation above by four without producing vulgar fractions because the minimum value of the index L is unity. The equation then becomes:
185632 = 4.m^{2} + 2.m - 2^{2.L - 2}.[16.z^{2} + 24.z + 9]
The logical conclusion is that if the exponent: [2.L - 2] is now zero, then the above equation would have an even left side and an uneven right side. This is logically inconsistent and therefore [2.L - 2] is a positive even integer and we can divide each side of the above equation by two. This gives:
92816 = 2.m^{2} + m - 2^{2.L - 3}.[16.z^{2} = 24.z + 9]
The integer: [2.L - 3] cannot be zero because L is an integer. The conclusion is that m is an even integer. Let m = 2.h Substitution for m gives:
92816 = 2.[2.h]^{2} + [2.h] - 2^{2.L - 3}.[16.z^{2} + 24.z + 9]
This equation after division by two becomes:
46408 = 4.h^{2} + h - 2^{2.L - 4}.[16.z^{2} + 24.z + 9]
This equation is the first to satisfy the condition that h is uneven and [2.L - 4] is zero.
Therefore L = 2. Rewriting this equation:
46408 = 4.h^{2} + h - 16.z^{2} - 24.z - 9
Putting h = 2.j + 1, substituting and transferring the minus nine to the left side of the equation, we find:
46417 = 4.[2.j + 1]^{2} + [2.j + 1] - - 16.z^{2} - 24.z
This is:
46417 = 4.[4.j^{2} + 4.j + 1] + [2.j + 1] - 16.z^{2} - 24.z
Simplifying:
46417 = 16.j^{2} + 16.j + 4 + 2.j + 1 - 16.z^{2} - 24.z
This becomes:
46417 = 16.j^{2} + 18.j + 5 - 16.z^{2} - 24.z
Transferring the five to the left side of the equation gives:
46412 = 16.j^{2} + 18.j - 16.z^{2} - 24.z
Dividing each side of the above equation by two gives:
23206 = 8.j^{2} + 9.j - 8.z^{2} - 12.z
In the term: 9.j, the integer j has to be even because the left side of this equation is even.
Let j = 2.g. Substitution gives:
23206 = 8.[2.g]^{2} + 9.[2.g] - 8.z^{2} - 12.z
That is:
23206 = 32.g^{2} + 18.g - 8.z^{2} - 12.z
Division by two gives:
11603 = 16.g^{2} + 9.g - 4.z^{2} - 6.z
Because the left side is uneven, g has to be uneven as well. Let g = 2.X + 1 Substitution for g gives:
11603 = 16.[2.X + 1]^{2} + 9.[2.X + 1] - 4.z^{2} - 6.z
This becomes:
11603 = 64.X^{2} + 64.X + 16 + 18.X + 9 - 4.z^{2} - 6.z
Transferring the twenty-five to the left side of the equation gives:
11578 = 64.X^{2} + 82.X - 4.z^{2} - 6.z
Division by two gives:
5789 = 32.X^{2} + 41.X - 2.z^{2} - 3.z
In the above equation, we can substitute X = 2.Y + 1 and z = 2.H leaving one uneven integer on the right side of the equation. Substitution gives:
5789 = 32.[4.Y^{2} + 4.Y + 1] + 41.[2.Y + 1] - 2.[2.H]^{2} - 3.[2.H]
5789 = 128.Y^{2} + 128.Y + 32 + 82.Y + 41 - 8.H^{2} - 6.H
Simplifying gives:
5716 = 128.Y^{2} + 210.Y - 8.H^{2} - 6.H
Division by two gives:
2858 = 64.Y^{2} + 105.Y - 4.H^{2} - 3.H
Because the left side is even, [i] Y and H have each got to be even, or alternatively, [ii] Y and H have each got to be uneven. Trying alternative [i], let Y = 2.a and H = 2.b Substitution gives:
2858 = 256.a^{2} + 210.a - 16.b^{2} - 6.b
Division by two gives:
1429 = 128.a^{2} + 105.a - 8.b^{2} - 3.b
Either [i] a is uneven and b is even or exclusively a is even and b is uneven.
Making choice [i], let a = 2.W + 1 and b = 2.Z [upper case Z] Substitution gives:
1429 = 128.[4.W^{2} + 4.W + 1] + 105.[2.W + 1] - 8.[2.Z]^{2} - 3.[2.Z]
Simplifying:
1429 = 512.W^{2} + 512.W + 128 + 210.W + 105 - 32.Z^{2} - 6.Z
1196 = 512.W^{2} + 722.W - 32.Z^{2} - 6.Z
Division by two gives:
598 = 256.W^{2} + 361.W - 16.Z^{2} - 3.Z
The above equation is Diophantine with solutions: W = 1 and Z = 1
Check: 598 = 256 + 361 - 16 - 3 [this is correct]
It will be seen later that this is not the optimal Diophantine equation but this equation returns the correct values of M and K.
Reversing the substitutions gives: a = 3 and b = 2. Now Y = 2.a and H = 2.b. This gives: Y = 6 and H = 4. Next, X = 2.Y + 1 and z = 2.H [lower case z] This gives X = 13 and z = 8. Next, g = 2.X + 1. This gives g = 27. The substitution j = 2.g gives j = 54. Next, h = 2.j + 1 gives h = 109. Almost there, m = 218. Finally, M = [4.m + 1]. That is M = 873 [this is correct] K = 2^{L}.[4.z + 3]. Substitution for the known values, L = 2 and z = 8 gives: K = 140, that is K = 2^{2}.35 [this is correct]
But checking: q[1] = M - k = and q[2] = M + K gives: q[1] = 733 and q[2] = 1013.
The above Diophantine equation is not optimally Diophantine. Rewriting this equation:
598 = 256.W^{2} + 361.W - 16.Z^{2} - 3.Z
The left side of this equation is an even integer, 598. The logical conclusion is that [a] W and Z have to be each even, or the alternative is that [b] W and Z have to be each uneven. In Example [2], where Q = 2701, the uneven choice was used. The even choice, while resulting in a non Diophantine equation still gave the correct answers. taking then choice [b], the uneven choice, set: W = 2.u + 1 and Z = 2.v + 1. Using these substitutions, the equation becomes:
598 = 256.[4.u^{2} + 4.u + 1] + 361.[2.u + 1] - 16.[4.v^{2} + 4.v + 1] - 3.[2.v + 1]
Simplifying:
598 = 1024.u^[2} + 1024.u + 256 + 722.u + 361 - 64.v^[2} - 64.v - 16 - 6.v - 3
This becomes:
0 = 1024.u^{2} + 1746.u - 64.v^{2} - 70.v
Division by two presents the optimal Diophantine equation:
0 = 512.u^{2} + 873.u - 32.v^{2} - 35.v [the optimal Diophantine equation]
The obvious solutions are u = 0 and v = 0. Notice the coefficients of u and v and compare them with the known values of X[1] and X[2] of M and K, above. [typing to be continued]
Taking an approximation, 861.7 to the square root of 742529, classical factorization requires precisely one hundred and forty-eight long and shorter prime [excepting division by prime two [2], that is in a disjoint class of its own] decimal divisions at the most to find the prime factors. The solution by deduction invariably requires one division by four and in this example nine divisions by two to obtain the same result. The deductive solution is much more intricate than the classical solution.
Example 4
editfactorize Q = 27654689 [5009, 5521] [M = 5265, K = 256, L[2] = 8, X[1] = 5265, X[2] = 1. The congruencies of 27654689, 5265, and 1 are all unity [1]. The square root of 27654689 is 5285.77 approximately. This means that precisely six hundred and ninety-six long and shorter divisions by primes are required to find the prime factors by the classical procedure.
Solution: The starting equation is:
27654689 = [16.y^{2} + 8.y + 1] - 2^{2.L[2]}.[16.z^{2} + 8.z + 1]
This obviously becomes:
27654688 = 16.y^{2} + 8.y - 2^{2.L}.[16.z^{2} + 8.z + 1]
The purpose of doing this example is not primarily to see if the correct answer can be found but to count the number of operations required to arrive at the optimal Diophantine equation and identify the coefficients of the unknowns in this equation. [the correct answer is found]
Division by four gives:
6913672 = 4.y^{2} + 2.y - 2^{2.L - 2}.[16.z^{2} + 8.z + 1]
Dividing by two: [this is the first division by two] D1
3456836 = 2.y^{2} + y - 2^{2.L - 3}.[16.z^{2} + 8.z + 1]
The conclusion here is that since the left side is even and [2.L - 3] is uneven and therefore 2^{2.L - 3} is even that y has to be even. Let y = 2.j Substitution gives:
3456836 = 2.[2.j]^{2} + [2.j] - 2^{2.L - 3}.[16.z^{2} + 8.z + 1]
Simplifying gives:
3456836 = 8.j^{2} + 2.j - 2^{2.L - 3}.[16.z^{2} ...]
dividing by two gives:
1728418 = 4.j^{2} + j - 2^{2.L - 4}.[16.z^{2} ...] D2
Put j = 2.k Substitution gives:
1728418 = 16.k^{2} + 2.k - 2^{2.L - 4}.[16.z^{2} ...]
Dividing by two gives:
864209 = 8.k^{2} + k - 2^{2.L - 5}.[16.z^{2} ...] D3
Substitute k = 2.n = 1
864209 = 32.n^{2} + 32.n + 8 + 2.n + 1 - 2^{2.L - 5}.[16.z^{2} ...]
This becomes:
864200 = 32.n^{2} + 34.n - 2^{2.L - 5}.[16.z^{2} ...]
Dividing by two:
432100 = 16.n^{2} + 17.n - 2^{2.L - 6}.[16.z^{2} ... ] D4
Set n = 2.m
432100 = 64.m^{2} + 34.m - 2^{2.L - 6}.[16.z^{2} ... ]
Division by two gives:
216050 = 32.m^{2} + 17.m - 2^{2.L - 7}.[16.z^{2} ... ] D5
Set m = 2.p
216050 = 128.p^{2} + 34.p - 2^{2.L - 7}.[16.z^{2} ... ]
Division by two gives:
108025 = 64.p^{2} + 17.p - 2^{2.L - 8}.[16.z^{2} ... ] D6
Set p = 2.q + 1
108025 = 256.q^{2} + 256.q + 64 + 34.q + 17 - 2^{2.L - 8}.[16.z^{2} ... ]
This becomes:
107944 = 256.q^{2} + 290.q - 2^{2.L - 8}.[16.z^{2} ... ]
Division by two gives:
53972 = 128.q^{2} + 145.q - 2^{2.L - 9}.[16.z^{2} ... ] D7
Substitute q = 2.r
53872 = 512.r^{2} + 290.r - 2^{2.L - 9}.[16.z^{2} ... ]
Division by two gives:
26986 = 256.r^{2} + 145.r - 2^{2.L - 10}.[16.z^{2} ... ] D8
Substitute r = 2.s
26986 = 1024.s^{2} + 290.s - 2^{2.L - 10}.[16.z^{2} ... ]
Division by two:
13493 = 512.s^{2} + 145.s - 2^{2.L - 11}.[16.z^{2} ] D9
Put s = 2.t + 1:
13493 = 2048t^{2} + 2048.t + 512 + 290.t = 145 - 2^{2.L - 11}.[16.z^{2} ... ]
This simplifies to:
12836 = 2048.t^{2} + 2338.t - 2^{2.L - 11}.[16.z^{2} ... ]
Division by two:
6418 = 1024.t^{2} + 1169.t - 2^{2.L - 12}.[16.z^{2} ... ] D10
Put t = 2.u:
6418 = 4096.u^{2} + 2338.u - 2^{2.L - 12}.[16.z^{2} ... ]
Division by two:
3209 = 2048.u^{2} + 1169.u - 2^{2.L - 13}.[16.z^{2} ... ] D11
Substitute u = 2.v + 1:
3209 = 8192.v^{2} + 8192.v + 2048 + 2338.v + 1169 - 2^{2.L - 13}.[16.z^{2} ... ]
Simplifying:
- 8 = 8192.v^{2} + 10530.v - 2^{2.L - 13}.[16.z^{2} ... ]
Division by two:
- 4 = 4096.v^{2} + 5265.v - 2^{2.L - 14}.[16.z^{2} ... ] D12
Put v = 2.w:
- 4 = 16384.w^{2} + 10530.w - 2^{2.L - 14}.[16.z^{2} ... ]
Division by two:
- 2 = 8192.w^{2} + 5265.w - 2^{2.L - 15}.[16.z^{2} ... ] D13
Put w = 2.x:
- 2 = 32768.x^{2} + 10530.x - 2^{2.L - 15}.[16.z^{2} ... ]
Division by two:
- 1 = 16384.x^{2} + 5265.x - 2^{2.L - 16}.[16.z^{2} + 8.z + 1] D14
The term 2^{2.L - 16} is unity. Rewriting the equation with a simplification:
0 = 16384.x^{2} + 5265.x - 16.z^{2} - 8.z
The equation above is nearly the optimally Diophantine. The coefficients of x and z have each to be uneven integers for optimality.
Put x = 2.y:
0 = 65536.y^{2} + 10530.y - 16.z^{2} - 8.z
Division by two gives:
0 = 32768.y^{2} + 5265.y - 8.z^[2}- 4.z D15
Put y = 2.a:
0 = 131072.a^{2} + 10530.a - 8.z^{2} - 4.z
Division by two:
0 = 65536.a^[2} + 5265.a - 4.z^{2} - 2.z
Recycling the label: y and substituting: a = 2.y:
0 = 262144.y^{2} + 10530.y - 4.z^{2} - 2.z
Division by two:
0 = 131072y^[2} + 5265.y - 2.z^{2} - 1.z [the optimal Diophantine equation] D16
Note that in this example, the number of divisions by two is equal to twice the integer L.
The coefficient of y is X[1] and the coefficient of z is X[2] in the difference of two squares.
...............................................................................................
Example 5
editFactorize Q = 15 [3, 5] [M = 4, K = 1, L[1] = 2, X[1] = 1, X[2] = 1 The congruencies of 15, and 1 are respectively three [3] and unity [1]]
Solution: the starting equation is:
15 = 2^{2.L[1]}.[16.y^{2} + 8.y + 1] - [16.z^{2} + 8.z + 1]
That is:
16 = 2^{2.L}.[16.y^{2} + 8.y + 1] - 16.z^{2} - 8.z
The solutions to be found deductively for L[1], y and z are respectively: [2, 0, 0].
Division by four:
4 = 2^{2.L - 2}.[16.y^{2} + 8.y + 1] - 4.z^{2} - 2.z
Division by two gives:
2 = 2^{2.L - 3}.[16.y^{2} + 8.y + 1] - 2.z^{2} - z
Substitution of z = 2.w gives:
2 = 2^{2.L - 3}.[16.y^{2} + 8.y + 1] - 8.w^{2} - 2.w
Division by two gives:
1 = 2^{2.L - 4}.[16.y^{2} + 8.y + 1] - 4.w^{2} - w
An explanation as to why it is justifiable to equate the exponent of two to zero is given below. If [2.L - 4] is not equated to zero but divisions by two continued, then equations similar to the starred equations would result. Then [2.L - 4] = 0 and 2^{2.L - 4} = 1. Rewriting the equation above:
1 = 16.y^{2} + 8.y + 1 - 4.w^{2} - w, or:
0 = 16.y^{2} + 8.y - 4.w^{2} - w
Substitute w = 2.u because w has to be even.
0 = 16.y^{2} + 8.y - 16.u^{2} - 2.u
Division by two gives:
0 = 8.y^{2} + 4.y - 8.u^{2} - u
Substitute u = 2.v because u has to be even.
0 = 8.y^{2} + 4.y - 32.v^{2} - 2.v
Division by two gives:
0 = 4.y^{2} + 2.y - 16.v^{2} - v
Substitute v = 2.t because v has to be even.
0 = 4.y^{2} + 2.y - 64.t^{2} - 2.t
Division by two gives:
0 = 2.y^{2} + 1.y - 32.t^{2} - 1.t [the optimal Diophantine equation]
The coefficients of y and t are respectively X[1] and X[2]. With L = 2, the prime factors are:
q[1] = [2^{2}.1 - 1] and q[2] = [2^{2}.1 + 1]. That is: q[1] = 3 and q[2] = 5.
In every one of the examples: [1, .. 5], the coefficient of X[2] has a minus sign, but this appears to have no significance. The two solutions of the optimal Diophantine equation in every one of the examples has been found to be zero. This does not seem to have any significance either.
Discussion
editDiscrimination between a false value of integer, L and the true value, where false values are less than the true value. [the exception to this situation is the occurrence of L equal to unity] The value, L = 1 could be false. For instance in Example 4, rewriting an equation at a stage in the progressive solution, we have:
26986 = 256.r^{2} + 145.r - 2^{2.L - 10}.[16.z^{2} + 8.z + 1]
Assume that L = 5, a false value of L. Rewriting this equation:
26986 = 256.r^{2} + 145.r - 16.z^{2} - 8.z - 1, or:
26987 = 256.r^{2} + 145.r - 16.z^{2} - 8.z
The immediate conclusion is that r is uneven. Setting r = 2.s + 1:
26987 = 1024.s^{2} + 1024.s + 256 + 290.s + 145 - 16.z^{2} - 8.z
Simplifying:
26586 = 1024.s^{2} + 1314.s - 16.z^{2} - 8.z
Division by two: ............
13293 = 512.s^{2} + 657.s - 8.z^{2} - 4.z
Let s = 2.t + 1 Substitution gives:
13293 = 512.[4t^{2} + 4.t + 1] + 657.[2.t + 1] - 8.z^{2} - 4.z
Simplifying:
13293 = 2048.t^{2} + 2048.t + 512 + 1314.t + 657 - 8.z^{2} - 4.z
This becomes:
12124 = 2048.t^{2} + 3362.t - 8.z^{2} - 4.z
Division by two:
6062 = 1024.t^{2} + 1681.t - 4.z^{2} - 2.z
Substituting t = 2.u:
6062 = 4096.u^{2} + 3362.u - 4.z^{2} - 2.z
Division by two:
3031 = 2048.u^{2} + 1681.u - 2.z^{2} - 1.z *****************
In this equation, either: [a] u is even and z is uneven, or exclusively, [b] u is uneven and z is even.
Taking option [a] first. Let u = 2.v and z = 2.w + 1. Substitution gives:
3031 = 8192.v^{2} + 3362.v - 8.w^{2} - 10.w - 3
Simplifying:
3034 = 8192.v^{2} + 3362.v - 8.w^{2} - 10.w
Division by two gives:
1517 = 4096.v^{2} + 1681.v - 8.w^{2} - 5.w *****************
The two equations with asterisks adjacent have precisely the same logical structure. The integer on the left is uneven. The terms on the right involving the unknowns to the first power have uneven coefficients and therefore we could substitute one of the unknowns with an even substitution and the other unknown with an uneven substitution in order to make the equation seen to be logically correct. The predictable result is an equation again having the same logical structure as the two starred equations. This is an irreducible situation and we can conclude that the assumption that L = 5 was false. Just to make sure, we could substitute: v = 2.x and w = 2.y + 1. This gives:
1517 = 16384.x^{2} + 3362.x - 8.[4.y^{2} + 4.y + 1] - 5.[2.y + 1]
This becomes:
1517 = 16384.x^{2} + 3362.x - 32.y^{2} - 32.y - 8 - 10.y - 5
Simplifying gives:
1530 = 16384.x^{2} + 3362.x - 32.y^{2} - 42.y
Division by two:
765 = 8192.x^{2} + 1681.x - 16.y^{2} - 21.y *******************
In this equation either, [a] x is even and y is uneven, or exclusively [b] x is uneven and y is even. The above equation has been starred as it has the same logical structure as the other starred equations. The left side integer is becoming smaller for each substitution. Continuing, let x = 2.a and y = 2.b + 1. Substituting for x and y gives:
765 = 32768.a^{2} + 3362.a - 16.[4.b^{2} + 4.b + 1] - 21.[2.b + 1]
Simplifying gives:
765 = 32768.a^{2} + 3362.a - 64.b^{2} - 64.b - 16 - 42.b - 21
This becomes:
802 = 32768.a^{2} + 3362.a - 64.b^{2} - 106.b
Division by two:
401 = 16384.a^{2} + 1681.a - 32.b^{2} - 53.b ****************
The above equation has the same logical structure as the previous starred equations. Putting: a = 2.c and b = 2.d + 1 preserves as above, the logical truth of the equation. substitution gives:
401 = 65536.c^{2} + 3362.c - 32.[4.d^{2} + 4.d + 1] - 53.[2.d + 1]
The above integer on the left will eventually go negative, but the logical structure of the equation will remain identical to that of the starred equations and stay unaltered. The starred equations are logically invariant in the sense that any number of substitutions that preserve the logical validity do not change the logical structure of the equations.
Simplifying:
401 = 65536.c^{2} + 3362.c - 128.d^{2} - 128.d - 32 - 106.d - 53
This becomes:
486 = 65536.c^{2} + 3362.c - 128.d^{2} - 234.d
Division by two gives:
243 = 32768.c^{2} + 1681.c - 64.d^{2} - 117.d *************
Substituting: c = 2.e and d = 2.f + 1:
243 = 131072.e^{2} + 3362.e - 64.[4.f^{2} + 4.f + 1] - 117.[2.f + 1]
Simplifying:
243 = 131072.e^{2} + 3362.e - 256.f^{2} - 256.f - 64 - 234.f - 117
This becomes:
424 = 131072.e^{2} + 3362.e - 256.f^{2} - 490.f
Division by two:
212 = 65536.e^{2} + 1681.e - 128.f^{2} - 245.f
Set e = 2.j and f = 2.k
212 = 262144.j^{2} + 3362.j - 512.k^{2} - 490.k
Division by two gives:
106 = 131072.j^{2} + 1681.j - 256.k^{2} - 245.k
Substitute: j = 2.m and k = 2.n
106 = 524288.m^{2} + 3362.m - 1024.n^{2} - 490.n
Division by two gives:
53 = 262144.m^{2} + 1681.m - 512.n^{2} - 245.n ***********
A further substitution in to the above equation would require that either [a] m is even and n is uneven or exclusively [b] m is uneven and n is even. This situation seems to recur indefinitely. The important matter here is that the starred equations do not provide the solution to the values of X[1] and X[2]. At the very first appearance of an equation of the same logical form as a starred equation, the assumption that index L had the particular value at that stage of the solution was a false assumption.
It can be said that a starred equation and the optimal Diophantine equation are logical opposites. The optimal Diophantine equation is logically invariant as well as any of the starred equations.
Solving for the True Value of Integer, L.
After division of the simplified starting equation by four which is permissible because by hypothesis, Q is modulo four, having the appropriate congruency, then after two subsequent divisions by two, the exponent of two in the even term: [2.L - 2 - 2.J] should be equated to zero. This term: 2^{2.L - 2 - 2.J } supposed equal to unity is then dumped. A logical substitution, simplification and a division by two is carried out. This is repeated until we have either the optimal Diophantine equation or exclusively an equation of the form denoted by the asterisks [starred to the right]. If the equation was the optimally Diophantine, then the factorization has effectively been accomplished. If the equation, [usually after a very few substitutions and successive divisions by two] has the logical form of the starred equations, then the assumed value of L was false. The term 2^{2.L - 2 - 2.J} is reinstated and further substitutions and successive division carried out until the exponent becomes: [2.L - 2 - 2[J + 1]]. This is then equated to zero so that the term: 2^{2.L - 2 - 2.[J + 1]} is unity. The above process repeated. Eventually, no equation of the starred form appears but only the optimal Diophantine equation. The integer, L and the values of X[1] and X[2] from the coefficients in the optimal Diophantine provide the information to reconstruct the prime factors of Q. This is seen in the examples.
Since in Example 2, [Q = 2701] the values of M, K and L were known in advance, then for the sake of illustrating the result at the first crisis, the true option has been selected. Continuing in this way, the final equation using the proper options is Diophantine and the solutions returned the true values of M and K. A procedure has been found to discriminate between the false option [to be rejected] and the true option [to be accepted].
Finding the Proper Substitution at the First Crisis
editIt should be stated that if at the first crisis, the proper option has not been chosen, then the situation goes from bad to worse with ever more intractable equations.
The resolution of the first crisis depends on identifying the logical form of the equation produced by the true option and the false option. There were two wrong choices and two right choices. The right choices involved an even integer on the left side of the equation and led quite naturally to two different Diophantine equations. The solution or either Diophantine equation returned the correct values for M and K.
By logical form is meant the evenness or unevenness of the terms in an equation that determines the evenness or unevenness to be assigned to the unknowns in order that the equation should not be a logical contradiction.