Number of Prime Factors

I have noticed something about the "number of prime factors" of certain numbers. I was not a math major in college and don't have formal education in number theory, so I thought I would present it to the math wizards in the forum here and see what you-all think.

Define NPF(n) as being the number of prime factors of the integer n.

Ex: Given that 24 = 2³*3; then NPF(24) == 4.

Defining, as usual, that p_i is the ith prime number then I notice that for any p_i the NPF of (p_i²-1) is always unusually large, and for example, seems to be always larger than (p_i²+1).

Ex.: The number 17 is prime. 17²+1 =290 and 290 =2*5*29 and thus has three prime factors. But 17²-1 =288 and 288= 2⁵*3² and thus has 7 prime factors.

Here is a table of the number of prime factors of (p² -1) and (p² +1) for the first 60 prime numbers and for one larger prime number of interest.

Prime, p	NPF of (p2-1)	NPF of (p2+1)
2	1	1
3	3	2
5	4	2
7	5	3
11	5	2
13	5	3
17	7	3
19	6	2
29	6	2
31	8	3
37	6	3
41	7	3
43	6	4
47	7	4
53	7	3
59	6	2
61	6	2
67	6	3
71	8	2
73	7	4
79	8	2
83	6	4
89	8	3
97	9	3
101	7	2
103	7	3
107	7	4
109	8	3
113	8	3
127	11	3
131	7	2
137	7	3
139	7	2
149	7	3
151	8	3
157	6	5
163	8	3
167	7	3
173	6	4
179	7	3
181	8	2
191	10	4
193	9	5
197	8	3
199	9	2
211	7	3
223	9	3
227	6	3
229	7	3
233	8	4
239	10	5
241	9	3
251	8	4
257	11	4
263	7	3
269	9	3
271	10	2
277	6	3
281	8	3
8191	19	4

I know this is not a large number of primes that I have looked at so far, but. . . .

1. I conjecture that NPF(p_i²-1) is always larger than NPF(p_i²+1) -for primes >2. I have no idea why.

2. I notice that NPF(p²-1) is always 6 or greater for primes that are higher than 13 -at least for the sample that I have investigated. I wonder if that continues.

3. I also notice that any prime number that is one off from a power of 2 has an anomalously large number of prime factors.

Ex: 17 (=2⁴+1) is the lowest prime to for which NPF(p²-1) > 5: it has 7 prime factors.
Ex: 31 (=2⁵-1) and the NPF(31²-1) = 8
Ex: 127 (=2⁷-1) and the NPF(127²-1) = 11
Ex: 257 (=2⁸+1) and the NPF(257²-1) = 11
Ex: 8191 (=2¹⁵-1) and the NPF(8191²-1) = 19. 8191²-1 = 2¹⁴*3²*5*7*13

Comments, please!!!!!

Not much to add here, but note that in your first conjecture that p-i squared minus 1 (sorry, not figuring out sub and superscripts) is a difference of squares with factors p-1 and p+1. Not sure how that works into anything, but noticed that.

Quote: rsactuary

(sorry, not figuring out sub and superscripts)

To do p_i, use p[sub]i[/sub]

To do p², use p[sup]2[/sup]

You can also use ^ as an equivalent for superscripts when referring to raising a numbe to a power - i.e. p^2 = p²

Quote: gordonm888

2. I notice that NPF(p²-1) is always 6 or greater for primes that are higher than 13 -at least for the sample that I have investigated. I wonder if that continues.

Notice that all primes > 3 are either one more than a multiple of 6 or one less than a multiple of 6.
(Proof: every integer = one of 0, 1, 2, 3, 4, or 5 modulo 6; numbers = 0, 2, or 4 modulo 6 are multiples of 2; numbers = 3 modulo 6 are multiples of 3)

If p is one more than a multiple of 6, (6k + 1)² - 1 = 36 k² + 12 k = 2 x 2 x 3 x k x (3k + 1)
If p is one less than a multiple of 6, (6k - 1)² - 1 = 36 k² - 12 k = 2 x 2 x 3 x k x (3k - 1)
Either k is even or 3k +/- 1 is even, so there is another prime factor 2, which means there must be at least 6 prime factors.

...unless k = 2, 3k - 1 = 2 (in which case, k =1), or 3k + 1 = 2 (which is impossible as k = 1/3)
If k = 2, then (6k + 1)² - 1 = 168 = 2 x 2 x 2 x 3 x 7, and (6k - 1)² - 1 = 120 = 2 x 2 x 2 x 3 x 5, both of which have only 5 prime factors
If k + 1 = 2, then (6k - 1)² - 1 = 24 = 2 x 2 x 2 x 3, which is only 4 prime factors
However, if p > 13, then k >= 3

I must be missing something. Looking just at your first data row (p=2), I think p²-1=3 and p²+1=5.

Why are your NPF for these 1 and 0 rather than 1 and 1?

Quote: Doc

I must be missing something. Looking just at your first data row (p=2), I think p²-1=3 and p²+1=5.

Why are your NPF for these 1 and 0 rather than 1 and 1?

That's a typo. I will fix that. Thanks.

Quote: ThatDonGuy

Quote: gordonm888

2. I notice that NPF(p²-1) is always 6 or greater for primes that are higher than 13 -at least for the sample that I have investigated. I wonder if that continues.

Notice that all primes > 3 are either one more than a multiple of 6 or one less than a multiple of 6.
(Proof: every integer = one of 0, 1, 2, 3, 4, or 5 modulo 6; numbers = 0, 2, or 4 modulo 6 are multiples of 2; numbers = 3 modulo 6 are multiples of 3)

If p is one more than a multiple of 6, (6k + 1)- 1 = 36 k² + 12 k = 2 x 2 x 3 x k x (3k + 1)
If p is one less than a multiple of 6, (6k - 1)² - 1 = 36 k² - 12 k = 2 x 2 x 3 x k x (3k - 1)
Either k is even or 3k +/- 1 is even, so there is another prime factor 2, which means there must be at least 6 prime factors.

...unless k = 2, 3k - 1 = 2 (in which case, k =1), or 3k + 1 = 2 (which is impossible as k = 1/3)
If k = 2, then (6k + 1)² - 1 = 168 = 2 x 2 x 2 x 3 x 7, and (6k - 1)² - 1 = 120 = 2 x 2 x 2 x 3 x 5, both of which have only 5 prime factors
If k + 1 = 2, then (6k - 1)² - 1 = 24 = 2 x 2 x 2 x 3, which is only 4 prime factors
However, if p > 13, then k >= 3

Yes, I see. Simple, but brilliant. So, this observation is pretty pedestrian?

And, this implies that for any non-prime of the form n=6k +/- 1 -such as 25 or 35, that n² -1 will also have at least 6 prime factors. So, it really has nothing to do with whether n is a prime. It means that at least 1/3 of all numbers of the form n² -1 will have at least 6 prime factors.

And, I imagine that if n= 2^m +/- 1 there is some analogous analysis that would imply large numbers of prime factors for n² -1. I'll try to puzzle it out.

Quote: rsactuary

Not much to add here, but note that in your first conjecture that p-i squared minus 1 (sorry, not figuring out sub and superscripts) is a difference of squares with factors p-1 and p+1. Not sure how that works into anything, but noticed that.

Well this is interesting too. Don has worked out that p² -1 must have at least 6 prime factors, and rsactuary points out that p² -1 = (p+1)*(p-1). So this means that the numbers immediately above or below a prime (i.e, p+1 and p-1) cannot both be semiprimes.

I guess that's sensible. Both p+1 and p-1 must be divisible by 2 and one of them must be divisible by 3. So, assuming that neither p=1 or p-1 is exactly equal to 6, one of them must have a third factor - thus both p+1 and p-1 cannot be semiprimes.

Edit: Aha! Given p+1 and p-1, both numbers must be divisible by 2 and at least one of those numbers must be divisible by 2². Also either p+1 or p-1 must be divisible by 3, so if p-1 > 2*2*3 (or p>13) then both p+1 and p-1 must each have at least one additional prime factor, so that p²-1 must have a minimum of six prime factors because p²-1 must be divisible by 2^3*3 and by at least two additional prime numbers. Which is basically what Don said.

Quote: gordonm888

And, this implies that for any non-prime of the form n=6k +/- 1 -such as 25 or 35, that n² -1 will also have at least 6 prime factors. So, it really has nothing to do with whether n is a prime. It means that at least 1/3 of all numbers of the form n² -1 will have at least 6 prime factors.

Yes.

Quote: gordonm888

And, I imagine that if n= 2^m +/- 1 there is some analogous analysis that would imply large numbers of prime factors for n² -1.

If n = 2^m + 1, then n² - 1 = (n + 1)(n - 1) = (2^m + 2) 2^m = 2^m+1 (2^m-1 + 1)

If n = 2^m - 1, then n² - 1 = (n + 1)(n - 1) = 2^m (2^m - 2) = 2^m+1 (2^m-1 - 1)

In both cases, there are at least m + 2 prime factors, m + 1 of which are 2. Note that, in the second case, if m is odd and > 1, 2^m-1 - 1 is a multiple of 3.

Quote: gordonm888

And, I imagine that if n= 2^m +/- 1 there is some analogous analysis that would imply large numbers of prime factors for n² -1.

Quote: ThatDonGuy

If n = 2^m + 1, then n² - 1 = (n + 1)(n - 1) = (2^m + 2) 2^m = 2^m+1 (2^m-1 + 1)

If n = 2^m - 1, then n² - 1 = (n + 1)(n - 1) = 2^m (2^m - 2) = 2^m+1 (2^m-1 - 1)

In both cases, there are at least m + 2 prime factors, m + 1 of which are 2. Note that, in the second case, if m is odd and > 1, 2^m-1 - 1 is a multiple of 3.

Yes, yes. I agree. Got it.

Thinking out loud: Does this apply to all integers of the form n= 2^m +/- a^2k, with a =an integer?

delete duplicate.

Edit: Interesting that some of these numbers are Mersenne primes.

Quote: gordonm888

Thinking out loud: Does this apply to all integers of the form n= 2^m +/- a^2k, with a =an integer?

Doubtful, considering 2¹² + 7^2x4 = 5,768,897, which is prime
So is 32,687 = 2¹⁵ - 3^2x2

This is indeed interesting! I don't have any good comments offhand, but love how primes have strong correlations like this, but there is still no easy way to check whether a huge number is prime.

Quote: Wizard

This is indeed interesting! I don't have any good comments offhand, but love how primes have strong correlations like this, but there is still no easy way to check whether a huge number is prime.

It depends on what you mean by "easy." Lucas-Lehmer is simple enough, but (a) it only works on Mersenne primes (primes that are one less than a power of 2 - and note that the power to which 2 is raised has to be prime as well, as (2 raised to a nonprime power) minus 1 cannot be prime), and (b) it takes a long time; I think even the fastest computers at the moment need a month to test some numbers.

"The quick version" of Lucas-Lehmer: let N = 2^P - 1, where P is a prime. Let S₀ = 4, and for all positive integers K, S_K = (S_K-1² - 2) mod N. N is prime if and only if S_P-2 = 0.
Example: let P = 5; N = 31
S₁ = (4² - 2) mod 31 = 14
S₂ = (14² - 2) mod 31 = 8
S₃ = (8² - 2) mod 31 = 0
S_P-2 = 0, so 31 is prime

Quote: ThatDonGuy

Quote: gordonm888

Thinking out loud: Does this apply to all integers of the form n= 2^m +/- a^2k, with a =an integer?

Doubtful, considering 2¹² + 7^2x4 = 5,768,897, which is prime
So is 32,687 = 2¹⁵ - 3^2x2

But (5768897² -1) = 2⁷ * 3 * 7 * 73 * 79 * 163 * 13171. That is 13 prime factors!

And (32687²-1) = 2⁵ * 3² * 59 * 227 * 277. That is 10 prime factors.

But clearly since 'a' is these equations is not divisible by 2, we don't get as high an exponent on the 2 in the prime factors expression.

Quote: gordonm888

Quote: ThatDonGuy

Quote: gordonm888

Thinking out loud: Does this apply to all integers of the form n= 2^m +/- a^2k, with a =an integer?

Doubtful, considering 2¹² + 7^2x4 = 5,768,897, which is prime
So is 32,687 = 2¹⁵ - 3^2x2

But (5768897² -1) = 2⁷ * 3 * 7 * 73 * 79 * 163 * 13171. That is 13 prime factors!

And (32687²-1) = 2⁵ * 3² * 59 * 227 * 277. That is 10 prime factors.

But clearly since 'a' is these equations is not divisible by 2, we don't get as high an exponent on the 2 in the prime factors expression.

Oh, you mean (2^m +/- a^2k)² - 1, don't you? My bad...

slightly off topic, but for those that like number theory, there is a gentleman on YouTube that does daily math contest type questions. His knowledge is amazing.

Look up Michael Penn. Very informative and reminds me how much of my math knowledge I've lost since graduating 30 years ago.

Here's a problem involving primes.....

https://www.youtube.com/watch?v=G-bzYoKd5ms

One of my takeaways from all this is that (n² -m²) can never be prime because

(n² -m²) = (n + m) *(n - m).

Therefore, if you were wondering whether 57 was prime or not, you might discover that 57 = (11² -8²) and therefore cannot be prime. Indeed, 57 is 3 * 19 which is (11-8) * (11+8). And its obvious that every composite number can be expressed as (n² -m²) so once you have discovered a suitable n and m you know that (n + m) and (n - m) are factors.

Test for Primes/Factoring Non-Primes (questionable Efficiency.)

Let's say you want to be able test for primeness and determine prime factors for many numbers up to 10,000,000,000; 10E10.

Step 1. Calculate n^2 for all numbers 1 to 10E10 and list the values in ascending order in two look-up tables -one for odd values n^2 and the other for even values of n^2.

Step 2. Given an (odd) number X to be factored, subtract X from all values on the Even n^2 table that are greater than X and less than X^2.

Step. 3 Using a vlookup function or something equivalent, look to see if any of the differences between n^2 and X calculated in step 2 are on the odd table. If they are then you that discovered that X is not prime and you know from the two n^2 values what the two factors are, although those factors are not necessarily prime and may need to be factored further.

Step 4, Repeat Steps 2 and 3 but reverse the roles of the odd N^2 table and Even N^2 table.

Compared to a standard Erasthosthenes sieve where you divide a number X by all primes smaller than sqrt(x) this method has the following advantages:

1. It doesn't require you to know all the primes up to sqrt(X).

2. It substitutes a subtraction operation for the division operation used in the standard sieve technique. My impression is that subtraction of two long numbers is more computationally efficient than division (of two long numbers).

3. If you are undertaking a large number of factorizations the upfront work of calculating all the n^2 values is amortized over many tasks.

Additionally, you could use a hybrid sieve to make this more efficient. Example:

Given an X to test and factorize, first divide X by all prime numbers under 1000 (there are 168 of them). This will quickly identify the great majority of composite numbers under 10E10 as being composite and give you some factors for each successfully identified composite number and is ~0.01 of the maximum number of division operations in the Erastoshenes Sieve method. But by doing this first, it reduces the range of 1 to 10E10 on the precalculated tables of n^2 to instead be from 10E3 to 10E7 - that is a reduction of precalculated values by greater than a factor of 1000. This might make the whole thing more manageable.

Could this help factorize odd numbers that are 10^60 to 10^100? Oh God, probably not. But maybe there is a role.

For example if I am given a number X that has 64 digits -well I don't what the primes are in the range 10^20 to 10^32. But I can start looking at n^2 - X values for n>sqrt(x) and see if any of those n^2 - X differences are a square. I would have to be lucky to find one, but at least its possible.

LOL, I fully expect ThatDonGuy and others to critique this and explain why this is worse than Erastosthenes sieve. But at least give me credit for thinking . . .

Quote: gordonm888

LOL, I fully expect ThatDonGuy and others to critique this and explain why this is worse than Erastosthenes sieve. But at least give me credit for thinking . . .

Challenge accepted!

Doesn't your method make the assumption that every nonprime number can be expressed as the difference of two squares?

Try your method with X = 10. What happens?

Also, you need to make sure that if you do find two squares, they aren't consecutive, as otherwise one of your factors will be 1. Note that every positive odd number can be expressed as the difference of two (consecutive) primes.

Okay, again let's assume you have an integer X and you want to test to see whether there is a solution to

n² - m² = X

as a way to find factors of X.

I believe we can use modular arithmetic to develop selection rules so that we don't need to test all values of n and n² to see if an m² solution exists.

Any square of an integer is congruent with (0,1,4,5,6,9)mod10. Thus we know that m² cannot be congruent with (2,3,7,8)mod 10.

Now lets say that our mystery number X ends with a last digit of 7. We know that there will be no value of n² that ends in 9, 0, 4 or 5 that can satisfy the equation because that would require a value of m² that ends in 2,3,7 or 8.

- If n² cannot end in 9 then n cannot end in 3 or 7.
- If n² cannot end in 0 then n cannot end in 0.
- If n² cannot end in 4 then n cannot end in 2 or 8.
- If n² cannot end in 5 then n cannot end in 5.

So, given that X ends in 7, when searching for a set of (n,m) that satisfy the equation, we need only look at values of n that end in 1,4,6 or 9. We have effectively reduced the possibilities to look at by 60%!

If X ends in 1 then n cannot have a 2, 3, 7 or 8 as its last digit.
If X ends in 3 then n cannot have a 0, 1, 4, 5, 6 or 8 as its last digit.
If X ends in 9 then n cannot have a 1, 4, 6, or 9 as its last digit.

I suspect that if one went into a different number base one might be able to develop additional selection rules that could further eliminate values of n^2 that are possible solutions.

Quote: ThatDonGuy

Challenge accepted!

Doesn't your method make the assumption that every nonprime number can be expressed as the difference of two squares?

Try your method with X = 10. What happens?

I should have said that every ODD non prime number can be expressed as the difference of two squares. Even composite numbers are definitely not of the form (n^2 -m^2)

Since odd numbers are the only ones we would really be concerned with, I think that is sufficiently interesting.

Quote: ThatDonGuy

Also, you need to make sure that if you do find two squares, they aren't consecutive, as otherwise one of your factors will be 1.

Excellent point. Example: 8^2-7^2 =15 which has factors (8+7) and (8-7) which isn't very interesting.

So: X = n² - m²; n>m+1

What is interesting is mathematicians have forever been unable to find a polynomial expression that defines prime numbers. But the above polynomial expression defines all odd numbers that aren't prime.

Quote: ThatDonGuy

Note that every positive odd number can be expressed as the difference of two (consecutive) primes.

You lost me with this comment. The difference between two consecutive primes (ignoring 2) must be an even number. What did you mean to say?

Okay, let's continue to assume that you have an integer X and you want to test to see whether there is a solution to

n² - m² = X

as a way to find factors of X.

In my last post I used modular arithmetic to develop selection rules so that we don't need to test all values of n and n² to see if an m² solution exists. Namely:

1. If X ends in 7 then n cannot have a 0, 2, 3, 5, 7 or 8 as its last digit.
2. If X ends in 1 then n cannot have a 2, 3, 7 or 8 as its last digit.
3. If X ends in 3 then n cannot have a 0, 1, 4, 5, 6 or 8 as its last digit.
4. If X ends in 9 then n cannot have a 1, 4, 6, or 9 as its last digit.

I have just started to look at the last two digits of X.

Basically n² is congruent with (0, 1, 4, 9, 16, 21, 24, 25, 29, 36, 41, 49, 56, 61 64, 69, 76, 81, 84, 89, 96) mod100.

That is 22 of 100 numbers as residues of mod100.

When the last two digits of X are 07 then n is limited to the following two last digits: 4, 6, 14, 16, 24, 26, 34, 36, 44, 46, 54, 56, 64, 66, 74, 76, 84, 86, 94, 96. Basically, that means that n is limited to ending in 4 or 6! That reduces the possible values of n by 80%!

When the last two digits on X are 17, then n is limited to the following two last digits: 9, 19, 21, 29, 31, 41, 59, 69, 71, 79, 81 and 91. That only 12 numbers out of a possible 100 for the two last digits of n -an 88% reduction in numbers to sieve through.

That's all I've done so far. But it shows that we may be able to look at the last n digits of the number to be factorized and use selection rules to gain very significant efficiencies in terms of reducing the number of values of n that must be sieved through to solve n^2 - m^2 = X.

Update: I just looked at the rules for when the last two digits of X are 27 -and they are identical to the rules when the last two digits of X are 07.

Quote: gordonm888

You lost me with this comment. The difference between two consecutive primes (ignoring 2) must be an even number. What did you mean to say?

Every positive odd number can be expressed as the difference of the squares of two consecutive numbers.
Simple enough proof: every positive odd number is of the form 2N+1, where N is a nonnegative integer, and (N+1)² - N² = 2N+1.

Okay, let's continue to assume that you have an integer X and you want to test to see whether there is a solution to

n² - m² = X

as a way to find factors of X which are (n+m) and (n-m)

I have now worked out the rules for the last two digits of X; namely, dependent on the last two digits of X the possible values of n are limited to what is shown in the table below. These means that one can use the last two digits of the number you are trying to factor to speed up the sieve search for a suitable set of (m,n).

Last Two Digits of X	Last Two digits of n
01	x5, 01,49,51,99
03, 23, 43, 63, 83	x2, x8
07, 27, 47, 67, 87	x4, x6
09	x5, 03,47,53,97
11	x0, 06,44,56,94
13, 33, 53, 73, 93	x3, x7
17, 37, 57, 77, 97	x1, x9
19	x0, 12,38,62,88
21	x5, 11,39,61,89
29	x5, 23,27,73,77
31	x0, 16,34,66,84
39	x0, 8,42,58,92
41	x5, 21,29,71,79,
49	x5, 7,43,57,93
51	x0, 24,26,74,76
59	x0, 22,28,72,78
61	x5, 19,31,69,81
69	x5, 13,37,63,87
71	x0, 14,36,64,86
79	x0, 02,48,52,98
81	x5, 09,41,59,91
89	x5, 17,33,67,83
91	x0, 3,47,53,97
99	x0, 18,32,68,82

Lots of symmetry in that table, isn't there?

So for some X the search for a suitable pair of (m,n) will be sped up by 80%, while for other X the search will be faster by 86%.

I think the reason I am so intrigued is because the sieve search can be made more efficient by looking at the last n digits of X.

I mean, in an Erasthosthenes sieve, one knows that numbers ending in 0,2,4,5,6, and 8 are not prime and that numbers whose digits sum to a multiple of 3 are also not prime. So, that even when if you don't have a priori knowledge of which potential divisors are prime, you can readily eliminate about 73% of all numbers as possible divisors to be tested by just looking at the digits. But that's about the end of the efficiency for Erasthosthenes. This method is already eliminating more than 73% and will be even more efficient if we develop rules based on the last 3 digits of X (or 4 or more.)

Of course, my proposed method has some other inefficiencies not common with Erasthosthenes. But let's keep plugging away.

I have added an additional column to the table from my last post. I am finding that modular nomenclature is an efficient way to represent the constraints on n.

Last Two Digits of X	Last Two digits of n	Required form of n
01	x5, 01,49,51,99	5(mod10), ±1(mod 50)
03, 23, 43, 63, 83	x2, x8	2, 8(mod10)
07, 27, 47, 67, 87	x4, x6	4, 6(mod10)
09	x5, 03,47,53,97	5(mod10), ±3(mod 50)
11	x0, 06,44,56,94	0(mod10), ±6(mod 50)
13, 33, 53, 73, 93	x3, x7	3,7(mod10)
17, 37, 57, 77, 97	x1, x9	1, 9(mod10)
19	x0, 12,38,62,88	0(mod10), ±12(mod 50)
21	x5, 11,39,61,89	5(mod10), ±11(mod 50)
29	x5, 23,27,73,77	5(mod10), ±23(mod 50)
31	x0, 16,34,66,84	0(mod10), ±16(mod 50)
39	x0, 8,42,58,92	0(mod10), ±8(mod 50)
41	x5, 21,29,71,79,	5(mod10), ±21(mod 50)
49	x5, 7,43,57,93	5(mod10), ±7(mod 50)
51	x0, 24,26,74,76	0(mod10), ±24(mod 50)
59	x0, 22,28,72,78	0(mod10), ±22(mod 50)
61	x5, 19,31,69,81	5(mod10), ±19(mod 50)
69	x5, 13,37,63,87	5(mod10), ±13(mod 50)
71	x0, 14,36,64,86	0(mod10), ±14(mod 50)
79	x0, 02,48,52,98	0(mod10), ±2(mod 50)
81	x5, 09,41,59,91	5(mod10), ±9(mod 50)
89	x5, 17,33,67,83	5(mod10), ±17(mod 50)
91	x0, 3,47,53,97	0(mod10), ±3(mod 50)
99	x0, 18,32,68,82	0(mod10), ±18(mod 50)

Well, I see that I have taken a wrong turn. I should be searching for values of m rather than values of n.

Again, the basic idea is, for a given integer X to search for values of (m,n) that satisfy X=n² - m²; n-m >1 because that means that (n+m) and (n-m) are factors of X.

Now obviously n² > X and n² > m² but is m² < X? If m<sqrt(X) then searching for m between 0 and sqrt(X) will be sufficient to find m.

Ex: 1000² - 989² = 21 879 and sqrt(21879) ~ 147.92. Here m=989 >147.92 so searching for m between 0 and sqrt(X) is not going to find this value of m.

However, 21 879 = 3*3*11*13*17 and thus will have many sets of (m,n) that satisfy X=n² - m²; n-m >1. This is because we can combine the prime factors in different ways to make multiple values of (m+n,m-n). For example, 21 879 = 160² - 61² and also 152² - 35². And both of those (m,n) pairs have an m< sqrt(X).

What if X is a semiprime, i.e., a product of only two prime factors? Then there will only be one (m,n) pair that satisfies X=n² - m²; n-m >1. And I think I have convinced myself that in case of a semiprime X that m< sqrt(X). And if that is the case then any X with many prime factors must also have one or more (m,n) pairs where m < sqrt(X).

Thus we can restrict ourselves to the range 0 to sqrt(x) when looking for at least one suitable m that solves our equation. And that should be an easier task than looking for n in the range of numbers greater than sqrt(X)!

The selection rules for searching for m are closely related to the rules for searching for n, but are not the same. They will likely involve the same efficiencies though. But I will need to recalculate new rules.

The main method that I have been 'discovering' here is already well established in number theory. Looking for solutions to n=X² - Y² as a way to factor n is called Fermat's Factorization method Then, using one of several different approaches with modular arithmetic to make the search more efficient is the "conguence of squares" method. Congruence_of_squares or Dixon's_factorization_method or a variant of Dixon's method called the Quadratic Sieve Quadratic_sieve.

The method I have been using with modular arithmetic appears to be different in it specific aspects than any of these other methods, but may wind up effectively being either the Dixon method or the Quadratic Sieve (QS) method. The QS method was the fastest method for factorization of large numbers up until the early 1990's when the Number Field Factorization method was developed and shown to be faster. The QS method is still the second fastest factorization method for large numbers.

As I've said, I've never had a course in number theory so I often discover things that turn out to be well known. This idea was not a dumb idea, I'm just not the first to think of it, lol.