mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-12-07, 22:45   #1
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7·13·17 Posts
Default How often is 2^p-1 square-free

If p is prime, how often is 2^p-1 square-free?

Here is the background to my question: Fix a prime q. It is well known that a^{q-1} is congruent to 1 mod q, if q does not divide a. However, it can also happen that a^{q-1} is congruent to 1 mod q^2. We can in fact find all such a (up to a multiple of q^2) rather easily.

We can continue this process, with q^3, q^4, etc... The size of possible a's grows at about the same rate.

So, if we fix a equal to some number (like 2) it seems unlikely that 2^p will be congruent to 1 mod q^2 (where p | (q-1)) for large q.

Is this a known result, or is my heuristic flawed?
Zeta-Flux is offline   Reply With Quote
Old 2005-12-07, 23:41   #2
John Renze
 
John Renze's Avatar
 
Nov 2005

24×3 Posts
Default

Quote:
Originally Posted by Zeta-Flux
If p is prime, how often is 2^p-1 square-free?
It is conjectured that all Mersenne numbers are squarefree.

http://primes.utm.edu/notes/proofs/SquareMerDiv.html

John
John Renze is offline   Reply With Quote
Old 2005-12-07, 23:46   #3
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

23·19 Posts
Default

Quote:
If p is prime, how often is 2^p-1 square-free?
This is currently an open question. In fact every Mersenne number with prime exponent examined so far has been square free. The following is known.

Definition: A prime q such that 2^{q-1} \equiv 1 \pmod {q^2} is known as a Wieferich prime.

Theorem: Let q be a prime such that q^2 divides 2^p-1 for some prime p. Then 2^{\frac{q-1}{2}} \equiv 1 \pmod {q^2} and so q is a Wieferich prime.

Proof: Since q divides 2^p-1, we have q=2kp+1 for some natural number k. So p=\frac{q-1}{2k}. Therefore 2^{\frac{q-1}{2k}} \equiv 2^p \equiv 1 \pmod {p^2}.

The only known Wieferich primes are 1093 and 3511 and there are no others less than 4 \cdot 10^{12}. Crandall, Dilcher, Pomerance, Math. Comp., 1997.

Something I'd also like to point out here is that if we didn't restrict the exponent to primes then there are lots of non-square-free Mersenne numbers. Let n be an odd natural number, then n^2 divides 2^{k \phi(n^2)}-1 for all natural numbers k. This follows straight from the Euler-Fermat theorem.

While it has been conjectured that all Mersenne numbers with prime exponents are square-free, it has also been conjectured that not all are square-free. Guy, Unsolved Problems in Number Theory, Springer, 1994. For this reason I describe it as an "open question," rather than a conjecture.
Dougy is offline   Reply With Quote
Old 2005-12-08, 04:01   #4
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

60B16 Posts
Default

Great. That is just the type of thing I'm looking for.

What I'd really like to know is if there is a similar finite set of examples where q^2 | 3^p-1, and a large lower bound they have tested up to.

(Same thing for 7^p -1 and 11^p -1...etc...)
Zeta-Flux is offline   Reply With Quote
Old 2005-12-12, 04:06   #5
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

93816 Posts
Default

Quote:
Originally Posted by Zeta-Flux
What I'd really like to know is if there is a similar finite set of examples where q^2 | 3^p-1, and a large lower bound they have tested up to.

(Same thing for 7^p -1 and 11^p -1...etc...)
I know of three examples of squares dividing p^q-1 for odd p and q less than 100

11^2 | 3^5
7^2 | 67^3
47^2 | 71^23

I also have some examples for larger values of p if that's of any interest. Also a few examples of cubed divisors.

Last fiddled with by wblipp on 2005-12-12 at 04:09
wblipp is online now   Reply With Quote
Old 2005-12-12, 04:31   #6
Citrix
 
Citrix's Avatar
 
Jun 2003

157610 Posts
Default

You forgot 3^2-1 %(2^3)==0

Only solution to a^x-b^y=1

Citrix
Citrix is offline   Reply With Quote
Old 2005-12-12, 11:00   #7
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7×13×17 Posts
Default

William,

Thanks. I found a paper by Peter Montgomery, giving the bounds I needed.

Cheers,
Pace
Zeta-Flux is offline   Reply With Quote
Old 2005-12-12, 12:08   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Which one is it?

Alex
akruppa is offline   Reply With Quote
Old 2005-12-12, 18:02   #9
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

60B16 Posts
Default

It is called "New Solutions of a^{p-1}\equiv 1\quad(\operatorname{mod} p^2), Mathematics of Computation, Vol. 61, No. 203, p. 361-363.

It is available online if you can get to mathscinet. It's a few years old now, and there is a more recent paper giving better bounds, but this one was good enough.

Last fiddled with by akruppa on 2005-12-12 at 23:49 Reason: added [tex] tags
Zeta-Flux is offline   Reply With Quote
Old 2005-12-12, 21:37   #10
fetofs
 
fetofs's Avatar
 
Aug 2005
Brazil

2·181 Posts
Default

Quote:
Originally Posted by Zeta-Flux
It is called "New Solutions of $a^{p-1}\equiv 1 (\operatorname{mod} p^2)$, Mathematics of Computation, Vol. 61, No. 203, p. 361-363.
Could some handy mod out there add the [tex] tags?
fetofs is offline   Reply With Quote
Old 2005-12-12, 22:05   #11
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7×13×17 Posts
Default

$a^{p-1}\equiv 1 (\operatorname{mod} p^2)$

Ah, so that's how to do it.

Last fiddled with by Zeta-Flux on 2005-12-12 at 22:06
Zeta-Flux is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
square free Mersenne Numbers? kurtulmehtap Math 0 2012-09-17 13:04
Perfect square or not? jnml Puzzles 12 2012-04-28 21:33
red square Fusion_power Puzzles 14 2008-04-25 11:37
Find a Square davar55 Puzzles 34 2007-06-12 14:17
Fast way to square??? maheshexp Math 2 2004-05-29 01:54

All times are UTC. The time now is 18:28.

Fri Dec 4 18:28:45 UTC 2020 up 1 day, 14:40, 0 users, load averages: 1.45, 1.45, 1.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.