mersenneforum.org Are any Mersenne factors 1 mod p^2?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2022-12-22, 00:01 #12 Andrew Usher   Dec 2022 23·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, 00:53 #13 alpertron     Aug 2002 Buenos Aires, Argentina 101111100102 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
2022-12-22, 15:12   #14
Dr Sardonicus

Feb 2017
Nowhere

24×3×7×19 Posts

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.
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.
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.

 2022-12-22, 23:09 #15 Andrew Usher   Dec 2022 23·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, 00:37   #16
charybdis

Apr 2020

1,021 Posts

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!

Last fiddled with by charybdis on 2022-12-23 at 00:38

2022-12-23, 02:35   #17
alpertron

Aug 2002
Buenos Aires, Argentina

2·761 Posts

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.

 2022-12-23, 23:19 #18 Andrew Usher   Dec 2022 23·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-24, 00:57   #19
charybdis

Apr 2020

3FD16 Posts

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.

2022-12-24, 14:30   #20
Dr Sardonicus

Feb 2017
Nowhere

24×3×7×19 Posts

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.

 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 q*q) which is a divisor of 2q - 1 for values of the exponent q less than 109. Most known prime factors are less than q*q. These factors cannot be congruent to 1 (mod q*q).
 2022-12-27, 01:59 #22 Andrew Usher   Dec 2022 23·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.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post bhelmes Number Theory Discussion Group 21 2021-09-15 02:07 ATH Miscellaneous Math 7 2020-10-09 11:09 bhelmes Miscellaneous Math 8 2020-09-14 17:36 tapion64 Miscellaneous Math 21 2014-04-18 21:02 CRGreathouse Math 5 2013-06-14 11:44

All times are UTC. The time now is 05:17.

Thu Jun 1 05:17:26 UTC 2023 up 287 days, 2:45, 0 users, load averages: 1.02, 1.07, 1.03

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔