How often is 2^p-1 square-free

Zeta-Flux · 2005-12-07, 22:45

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?

John Renze · 2005-12-07, 23:41

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

Dougy · 2005-12-07, 23:46

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.

Zeta-Flux · 2005-12-08, 04:01

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

wblipp · 2005-12-12, 04:06

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.

Citrix · 2005-12-12, 04:31

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

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

Citrix

Zeta-Flux · 2005-12-12, 11:00

William,

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

Cheers,
Pace

akruppa · 2005-12-12, 12:08

Which one is it?

Alex

Zeta-Flux · 2005-12-12, 18:02

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.

fetofs · 2005-12-12, 21:37

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?

Zeta-Flux · 2005-12-12, 22:05

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

Ah, so that's how to do it.

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-12, 18:02	#9
Zeta-Flux May 2003 60B₁₆ 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, 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
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

2005-12-08, 04:01	#4
Zeta-Flux May 2003 7·13·17 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:31	#6
Citrix Jun 2003 3137₈ 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 60B₁₆ 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