Are any Mersenne factors 1 mod p^2? - Page 2

Andrew Usher · 2022-12-22, 00:01

Yes, that's right. I wonder how you could find that example in reasonable time; I checked it, knowing the exponent, at mersenne.ca, so it's an NP problem for me.

I do think it's normal in mathematics to mean 'prime factors' by the word 'factors'; composites are merely divisors. And that's the way I normally use the two words.

The last poster's second statement would imply his first one, but is clearly flawed as (even without this base-2 example) it would work for any base, and Sweety has just above provided a counterexample for base 10, and I had indicated how to produce infinitely many - any prime q = kp^2 + 1 has order dividing p (giving this property) in p out of q bases, in a repeating sequence, which reminds one of the similar fact regarding the bases in which any prime has the Wieferich property.

The reason I was thinking about this at all is a consideration of the probability of Mersenne numbers being prime. The 1/n rule for factors is the same as for random integers, so a Mersenne with no factors to a certain limit (>> the exponent) should have the same chance of being prime as a random integer with no factors below the same - almost.

If the potential factors have an additional constraint to be 1 mod n, their chance of being prime (and therefore, of being a factor) is raised by the factor n/(n-1), and so the chance of the whole number being prime changed by the inverse of that, or decreased by 1/n. So I correctly stated in my last thread here that the Eisenstein Mersennes have 2/3 the density (primality chance) of the Gaussian (and ordinary) Mersennes, as their possible factors are all 1 mod 3 (in addition to 1 mod p) while the other classes have no such restriction. The ordinary Mersennes, then, would have a 1/p lower chance assuming the title question true (which I now know it is), but if it were false, this difference would be exactly canceled.

alpertron · 2022-12-22, 00:53

From the output of https://www.mersenne.org/report_fact...hi=10000&txt=1 , I've written a 10-line program in UBASIC that parses the lines and then prints the lines for which the second number (the prime factor of Mersenne number) modulo the first number (the Mersenne exponent) squared equals 1.

In this case there was no output, so I retried with limits 10000-20000, 20000-30000, 30000-40000 and so on, until the program found the solution I posted with exponent 93077.

To make the manual loop faster, I pressed CTRL-A, CTRL-C to copy all characters from mersenne.org , and then CTRL-A, CTRL-V in Notepad++ to paste the contents there, deleting the old data. I also deleted manually the header and the footer, so the program in UBASIC only had to parse the comma separated numbers.

Notice that this method misses the largest prime factor when the Mersenne number is completely factored.

Since I just wanted to find an example and this method included manual operations, it is possible that not all ranges were tested.

By the way, I continued the search for exponents up to one million, but I found no more examples.

Anyway, most of the prime factors of Mersenne numbers are unknown, so we are missing many possible candidates.

Dr Sardonicus · 2022-12-22, 15:12

Quote:

Originally Posted by Andrew Usher

<snip>
I do think it's normal in mathematics to mean 'prime factors' by the word 'factors'; composites are merely divisors. And that's the way I normally use the two words.
<snip>

In my experience, the term "factor" applied to an integer n > 1 is usually meant to mean a proper factor; that is, greater than 1 and less than n. This avoids trivialities such as the "factor" 1 of 2^p - 1 satisfying the condition of being congruent to 1 (mod p^2). "Factor" is frequently used to indicate an algebraic factor, particularly in the context of numbers like Cunningham numbers.

Quote:

The reason I was thinking about this at all is a consideration of the probability of Mersenne numbers being prime. The 1/n rule for factors is the same as for random integers, so a Mersenne with no factors to a certain limit (>> the exponent) should have the same chance of being prime as a random integer with no factors below the same - almost.
<snip>

It is generally accepted usage for the letter n to indicate an arbitrary positive integer, and p to specify a prime. If n is composite, the probability of 2^n - 1 being prime is zero.

There is a well-known conjecture about the "probability" (loosely speaking) of a Mersenne number with prime exponent being prime. For more details, I suggest you follow the links in this post while you still can.

In regard to numbers a^n - 1 with composite exponent, the prime factors of the "primitive part" are all congruent to 1 (mod n). See this paper for more details.

Andrew Usher · 2022-12-22, 23:09

I am already acquainted with the mathematical details you mention. I have seen the term 'proper factor' in the sense you mention but the adjective 'proper' is essential to it: if it were normal to use 'factor' alone to mean 'divisor', I think I would have noticed.

The word Mersenne numbers is usually taken as implying a prime exponent, so that composite exponents are not relevant to that. However, they always have algebraic parts that can be prime - which I'll loosely call cyclotomic numbers - and similar calculations can always be performed on them. It seems that the prime probability will always be <= the random-integer value, with equality exactly for Fermat numbers.

Possibly the source of some confusion is my reference to the '1/n rule'. This is the rule stating that you can expect a factor of n bits (or n digits in any base) to exist with probability 1/n approximately (it is actually an integral, of course). Deviations from that correspond exactly inversely to deviations in prime probability, as I am using it, since the e^gamma correction factor cancels.

alpertron: I didn't think of that; It would have been impossible without a queryable database. And that may well be the only known, as I calculate the number up to Mp to be O(log log p). Thansk for figuring it out, though.

charybdis · 2022-12-23, 00:37

Quote:

Originally Posted by Andrew Usher

I do think it's normal in mathematics to mean 'prime factors' by the word 'factors'; composites are merely divisors. And that's the way I normally use the two words.

Quote:

Originally Posted by Dr Sardonicus

In my experience, the term "factor" applied to an integer n > 1 is usually meant to mean a proper factor; that is, greater than 1 and less than n. This avoids trivialities such as the "factor" 1 of 2^p - 1 satisfying the condition of being congruent to 1 (mod p^2).

Quote:

Originally Posted by Andrew Usher

I have seen the term 'proper factor' in the sense you mention but the adjective 'proper' is essential to it: if it were normal to use 'factor' alone to mean 'divisor', I think I would have noticed.

I was always taught that "factor" and "divisor" were interchangeable and I have never seen anyone claim there is a distinction before. Sometimes one wants to exclude 1 and/or n, but that is often clear from context, e.g. if someone talks about two numbers with "no common factors" then they are referring to factors greater than 1. "Proper factor" can be a useful term as long as the meaning is clear; sometimes I've seen it used to refer to factors less than n, with 1 *included*, and indeed a Google search turns up both definitions within the first few results.

I have never seen "factor" used to refer only to prime factors without that being specified in advance.

Quote:

The word Mersenne numbers is usually taken as implying a prime exponent, so that composite exponents are not relevant to that.

Actually there is no clear agreement on the definition here, and once again both definitions can be found in the first few results of a Google search, along with pages which mention that both definitions exist!

alpertron · 2022-12-23, 02:35

Quote:

Originally Posted by Andrew Usher

alpertron: I didn't think of that; It would have been impossible without a queryable database. And that may well be the only known, as I calculate the number up to Mp to be O(log log p). Thansk for figuring it out, though.

I extended the search for exponents up to 5 million, but I found nothing.

Andrew Usher · 2022-12-23, 23:19

I don't think you need to go any farther, at least with the semi-manual method you specified. If you could automatically scan the entire database it might be different.

As to 'factor' vs. 'divisor', all I can say is that I have intuitively understood the distinction I gave for as long as I can remember, and I will continue to use them that way. Even if it's not actually standard, it doesn't _violate_ any standard, and is useful when talking about composite integers. In any case 'divisor' is used commonly when we do want to include everything; we say the sigma function is the 'sum of divisors', never the 'sum of factors'.

charybdis · 2022-12-24, 00:57

Quote:

Originally Posted by Andrew Usher

As to 'factor' vs. 'divisor', all I can say is that I have intuitively understood the distinction I gave for as long as I can remember, and I will continue to use them that way. Even if it's not actually standard, it doesn't _violate_ any standard, and is useful when talking about composite integers. In any case 'divisor' is used commonly when we do want to include everything; we say the sigma function is the 'sum of divisors', never the 'sum of factors'.

1. This does violate standards. You'll be hard pressed to find a mathematician who does not believe that 6 is a factor of 12. In schools, and therefore in examinations, the gcd is often referred to as the "greatest/highest common factor", and this would inevitably lead to confusion if some teacher had told their students that factors had to be prime.

2. Mathematics isn't going to come crashing down because we have two words for the same concept and some ambiguous terminology. Things aren't always defined in the way that would be most convenient, and most people have learnt to put that to one side and move on. I see that the moderators have given you a chance to do the same.

Dr Sardonicus · 2022-12-24, 14:30

Quote:

Originally Posted by Andrew Usher

As to 'factor' vs. 'divisor', all I can say is that I have intuitively understood the distinction I gave for as long as I can remember, and I will continue to use them that way.

Nobody gives a rat's patootie about what you "have intuitively understood," especially if it's in conflict with centuries of standard mathematical terminology.

If you don't moderate your antisocial behavior yourself and quit crapping up the Forum with your empty egocentrism voluntarily - well, moderators are called moderators for a reason.

alpertron · 2022-12-26, 18:29

I've written a batch file that includes curl to automate getting factors from Primenet. After 18 hours, I found no other prime of the form p=1 (mod q*q) which is a divisor of 2^q - 1 for values of the exponent q less than 10⁹.

Most known prime factors are less than q*q. These factors cannot be congruent to 1 (mod q*q).

Andrew Usher · 2022-12-27, 01:59

Done! That's one very special factor, then, and finding another might be of the same order of difficulty as finding a new Wieferich prime (assuming there is one).

It seems, as this thread has illustrated, that we can all go on as we are accustomed to and that any momentary confusion over 'factor' can be cleared up without hard feelings. I've been interested in math forever and had many discussions about it; I don't remember this ever causing difficulty. However, I probably overstated my case the first time, just out of surprise.

2022-12-22, 00:53	#13
alpertron Aug 2002 Buenos Aires, Argentina 10111110010₂ Posts	From the output of https://www.mersenne.org/report_fact...hi=10000&txt=1 , I've written a 10-line program in UBASIC that parses the lines and then prints the lines for which the second number (the prime factor of Mersenne number) modulo the first number (the Mersenne exponent) squared equals 1. In this case there was no output, so I retried with limits 10000-20000, 20000-30000, 30000-40000 and so on, until the program found the solution I posted with exponent 93077. To make the manual loop faster, I pressed CTRL-A, CTRL-C to copy all characters from mersenne.org , and then CTRL-A, CTRL-V in Notepad++ to paste the contents there, deleting the old data. I also deleted manually the header and the footer, so the program in UBASIC only had to parse the comma separated numbers. Notice that this method misses the largest prime factor when the Mersenne number is completely factored. Since I just wanted to find an example and this method included manual operations, it is possible that not all ranges were tested. By the way, I continued the search for exponents up to one million, but I found no more examples. Anyway, most of the prime factors of Mersenne numbers are unknown, so we are missing many possible candidates. Last fiddled with by alpertron on 2022-12-22 at 01:22

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
factors of Mersenne numbers	bhelmes	Number Theory Discussion Group	21	2021-09-15 02:07
Mersenne factors 2kp+1	ATH	Miscellaneous Math	7	2020-10-09 11:09
factors of Mersenne numbers	bhelmes	Miscellaneous Math	8	2020-09-14 17:36
Distribution of Mersenne Factors	tapion64	Miscellaneous Math	21	2014-04-18 21:02
Known Mersenne factors	CRGreathouse	Math	5	2013-06-14 11:44

2022-12-22, 00:01	#12
Andrew Usher Dec 2022 2³·5·11 Posts	Yes, that's right. I wonder how you could find that example in reasonable time; I checked it, knowing the exponent, at mersenne.ca, so it's an NP problem for me. I do think it's normal in mathematics to mean 'prime factors' by the word 'factors'; composites are merely divisors. And that's the way I normally use the two words. The last poster's second statement would imply his first one, but is clearly flawed as (even without this base-2 example) it would work for any base, and Sweety has just above provided a counterexample for base 10, and I had indicated how to produce infinitely many - any prime q = kp^2 + 1 has order dividing p (giving this property) in p out of q bases, in a repeating sequence, which reminds one of the similar fact regarding the bases in which any prime has the Wieferich property. The reason I was thinking about this at all is a consideration of the probability of Mersenne numbers being prime. The 1/n rule for factors is the same as for random integers, so a Mersenne with no factors to a certain limit (>> the exponent) should have the same chance of being prime as a random integer with no factors below the same - almost. If the potential factors have an additional constraint to be 1 mod n, their chance of being prime (and therefore, of being a factor) is raised by the factor n/(n-1), and so the chance of the whole number being prime changed by the inverse of that, or decreased by 1/n. So I correctly stated in my last thread here that the Eisenstein Mersennes have 2/3 the density (primality chance) of the Gaussian (and ordinary) Mersennes, as their possible factors are all 1 mod 3 (in addition to 1 mod p) while the other classes have no such restriction. The ordinary Mersennes, then, would have a 1/p lower chance assuming the title question true (which I now know it is), but if it were false, this difference would be exactly canceled.

2022-12-22, 23:09	#15
Andrew Usher Dec 2022 2³·5·11 Posts	I am already acquainted with the mathematical details you mention. I have seen the term 'proper factor' in the sense you mention but the adjective 'proper' is essential to it: if it were normal to use 'factor' alone to mean 'divisor', I think I would have noticed. The word Mersenne numbers is usually taken as implying a prime exponent, so that composite exponents are not relevant to that. However, they always have algebraic parts that can be prime - which I'll loosely call cyclotomic numbers - and similar calculations can always be performed on them. It seems that the prime probability will always be <= the random-integer value, with equality exactly for Fermat numbers. Possibly the source of some confusion is my reference to the '1/n rule'. This is the rule stating that you can expect a factor of n bits (or n digits in any base) to exist with probability 1/n approximately (it is actually an integral, of course). Deviations from that correspond exactly inversely to deviations in prime probability, as I am using it, since the e^gamma correction factor cancels. alpertron: I didn't think of that; It would have been impossible without a queryable database. And that may well be the only known, as I calculate the number up to Mp to be O(log log p). Thansk for figuring it out, though.

2022-12-23, 23:19	#18
Andrew Usher Dec 2022 2³·5·11 Posts	I don't think you need to go any farther, at least with the semi-manual method you specified. If you could automatically scan the entire database it might be different. As to 'factor' vs. 'divisor', all I can say is that I have intuitively understood the distinction I gave for as long as I can remember, and I will continue to use them that way. Even if it's not actually standard, it doesn't _violate_ any standard, and is useful when talking about composite integers. In any case 'divisor' is used commonly when we do want to include everything; we say the sigma function is the 'sum of divisors', never the 'sum of factors'.

2022-12-26, 18:29	#21
alpertron Aug 2002 Buenos Aires, Argentina 2·761 Posts	I've written a batch file that includes curl to automate getting factors from Primenet. After 18 hours, I found no other prime of the form p=1 (mod qq) which is a divisor of 2^q - 1 for values of the exponent q less than 10⁹. Most known prime factors are less than qq. These factors cannot be congruent to 1 (mod q*q).

2022-12-27, 01:59	#22
Andrew Usher Dec 2022 2³·5·11 Posts	Done! That's one very special factor, then, and finding another might be of the same order of difficulty as finding a new Wieferich prime (assuming there is one). It seems, as this thread has illustrated, that we can all go on as we are accustomed to and that any momentary confusion over 'factor' can be cleared up without hard feelings. I've been interested in math forever and had many discussions about it; I don't remember this ever causing difficulty. However, I probably overstated my case the first time, just out of surprise.