mersenneforum.org > Math How often is 2^p-1 square-free
 Register FAQ Search Today's Posts Mark Forums Read

 2005-12-07, 22:45 #1 Zeta-Flux     May 2003 7·13·17 Posts 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?
2005-12-07, 23:41   #2
John Renze

Nov 2005

24×3 Posts

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

2005-12-07, 23:46   #3
Dougy

Aug 2004
Melbourne, Australia

23·19 Posts

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.

 2005-12-08, 04:01 #4 Zeta-Flux     May 2003 60B16 Posts 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...)
2005-12-12, 04:06   #5
wblipp

"William"
May 2003
New Haven

93816 Posts

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

 2005-12-12, 04:31 #6 Citrix     Jun 2003 157610 Posts You forgot 3^2-1 %(2^3)==0 Only solution to a^x-b^y=1 Citrix
 2005-12-12, 11:00 #7 Zeta-Flux     May 2003 7×13×17 Posts William, Thanks. I found a paper by Peter Montgomery, giving the bounds I needed. Cheers, Pace
 2005-12-12, 12:08 #8 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Which one is it? Alex
 2005-12-12, 18:02 #9 Zeta-Flux     May 2003 60B16 Posts 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
2005-12-12, 21:37   #10
fetofs

Aug 2005
Brazil

2·181 Posts

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?

 2005-12-12, 22:05 #11 Zeta-Flux     May 2003 7×13×17 Posts $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

 Similar Threads Thread Thread Starter Forum Replies Last Post kurtulmehtap Math 0 2012-09-17 13:04 jnml Puzzles 12 2012-04-28 21:33 Fusion_power Puzzles 14 2008-04-25 11:37 davar55 Puzzles 34 2007-06-12 14:17 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