mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Are Mersenne numbers really square? (https://www.mersenneforum.org/showthread.php?t=23112)

 JM Montolio A 2018-02-28 12:10

Are Mersenne numbers really square?

What do you think about it ?

JMMA

 GP2 2018-02-28 15:56

You mean Mersenne numbers with prime exponents.

Nobody knows for sure.

If you ever find one that's non-square-free, then you automatically also find the third known Wieferich prime, and that would be a pretty big deal.

 CRGreathouse 2018-02-28 18:05

It's an interesting question. I seem to recall a weak consensus that there probably are Mersenne numbers with prime exponents which are not squarefree, but they may be extremely large. Does anyone here have an opinion?

 science_man_88 2018-02-28 18:39

[QUOTE=CRGreathouse;481174]It's an interesting question. I seem to recall a weak consensus that there probably are Mersenne numbers with prime exponents which are not squarefree, but they may be extremely large. Does anyone here have an opinion?[/QUOTE]
(Mod(1,3)*j*p^2+Mod(2,3)*p)*k^2+(Mod(1,3)*j*p+Mod(2,3))*k+Mod(1,3)*j roots mod 3 is what it comes down to partially.

 Dr Sardonicus 2018-02-28 20:17

[QUOTE=CRGreathouse;481174]It's an interesting question. I seem to recall a weak consensus that there probably are Mersenne numbers with prime exponents which are not squarefree, but they may be extremely large. Does anyone here have an opinion?[/QUOTE]
Many years ago, I heard that whether there are infinitely many Mersenne numbers that [i]are[/i] squarefree was an open question. I may be misremembering, but if that actually [i]is[/i] unknown, it would illustrate how difficult this sort of question may be.

Any non-squarefree Mersenne numbers with prime exponent certainly would be "extremely large," at least by my standards. As already pointed out, the exponent would be the next known Wieferich prime. The best known lower bound I could find in a quick online search was

[url=https://cs.uwaterloo.ca/journals/JIS/VOL14/Klyve/klyve3.pdf]A Wieferich Prime Search up to 6.7 × 10[sup]15[/sup][/url].

From the abstract,

[quote]This paper describes a new search algorithm for Wieferich primes using double-precision Montgomery arithmetic and a memoryless sieve, which runs significantly faster than previously published algorithms, allowing us to report that there are no other Wieferich primes p < 6.7 × 10[sup]15[/sup].[/quote]

 science_man_88 2018-02-28 20:21

[QUOTE=JM Montolio A;481185]JMMA[/QUOTE]

Do you know about clock math ? If not you may not understand responses.

 CRGreathouse 2018-02-28 21:01

[QUOTE=Dr Sardonicus;481187]Many years ago, I heard that whether there are infinitely many Mersenne numbers that [i]are[/i] squarefree was an open question. I may be misremembering, but if that actually [i]is[/i] unknown, it would illustrate how difficult this sort of question may be.[/QUOTE]

I could believe it! It's like abc implying infinitely many non-Wieferich primes. :smile:

[QUOTE=Dr Sardonicus;481187]Any non-squarefree Mersenne numbers with prime exponent certainly would be "extremely large," at least by my standards. As already pointed out, the exponent would be the next known Wieferich prime. The best known lower bound I could find in a quick online search was

[url=https://cs.uwaterloo.ca/journals/JIS/VOL14/Klyve/klyve3.pdf]A Wieferich Prime Search up to 6.7 × 10[sup]15[/sup][/url].[/QUOTE]

PrimeGrid got to [url=https://web.archive.org/web/20170707014426/http://prpnet.primegrid.com:13000/]6.071319 × 10[sup]17[/sup][/url] before they [url=https://www.primegrid.com/forum_thread.php?id=7436]suspended their search[/url] last May.

 GP2 2018-02-28 21:30

[QUOTE=Dr Sardonicus;481187]As already pointed out, the exponent would be the next known Wieferich prime.[/QUOTE]

It's not the exponent that would be the next Wieferich prime, but the non-square-free factor itself.

There is good reason to believe that all factors of size 64 bits or less of Mersenne exponents under 1 billion have already been found, either by TF or by user TJAOI, as well a considerable percentage of 65 bit factors. So all new Mersenne factors being discovered are in the 10[SUP]20[/SUP] range, which is beyond the range of the various exhaustive searches that were done by Dorais and Klyve, and I think also by PrimeGrid at one point.

So theoretically, every new factor we find has some infinitesimal chance of being the next Wieferich prime.

 Prime95 2018-02-28 21:56

[QUOTE=GP2;481194]
So theoretically, every new factor we find has some infinitesimal chance of being the next Wieferich prime.[/QUOTE]

The prim95 client and the PrimeNet server do not check for this. Perhaps mersenne.ca does (or could be upgraded to) check.

 GP2 2018-02-28 23:03

[QUOTE=Prime95;481198]The prim95 client and the PrimeNet server do not check for this. Perhaps mersenne.ca does (or could be upgraded to) check.[/QUOTE]

But it would be trivially easy to implement this. It's a small variation on the checking that's already done to verify a factor.

If [i]f[/i] is a factor of 2[SUP]p[/SUP]−1, then 2[SUP]p[/SUP] ≡ 1 (mod f).

In other words, that the modular exponentiation of (2,p,f) equals 1.

Modular exponentiation is available in various languages like PHP or Python, and also in the [URL="https://gmplib.org/manual/Integer-Exponentiation.html"]GMP library in the mpz_powm functions[/URL].

To check for Weiferich primes, you do the exact same thing, except using modulo f squared.

If the modular exponentiation of (2,p,f[SUP]2[/SUP]) ever equals 1, it's time to prepare a press release.

From time to time I've run a check over the entire database of factors, it can be done quite quickly. But it would be better to do it each time a factor is reported.

 a1call 2018-03-01 13:07

I think it is not impossible. So looking long enough should yield hits.
The Mersenne-Pseudoorimes are a subset of the more general form:
(k+1)^p-k^p
For positive integer k and prime p

As such
3^11-2^11 is divisible by 23^2

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