20051207, 22:45  #1 
May 2003
7·13·17 Posts 
How often is 2^p1 squarefree
If p is prime, how often is 2^p1 squarefree?
Here is the background to my question: Fix a prime q. It is well known that a^{q1} is congruent to 1 mod q, if q does not divide a. However, it can also happen that a^{q1} 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  (q1)) for large q. Is this a known result, or is my heuristic flawed? 
20051207, 23:41  #2  
Nov 2005
2^{4}·3 Posts 
Quote:
http://primes.utm.edu/notes/proofs/SquareMerDiv.html John 

20051207, 23:46  #3  
Aug 2004
Melbourne, Australia
2^{3}·19 Posts 
Quote:
Definition: A prime such that is known as a Wieferich prime. Theorem: Let be a prime such that divides for some prime . Then and so is a Wieferich prime. Proof: Since divides , we have for some natural number . So . Therefore . The only known Wieferich primes are 1093 and 3511 and there are no others less than . 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 nonsquarefree Mersenne numbers. Let be an odd natural number, then divides for all natural numbers . This follows straight from the EulerFermat theorem. While it has been conjectured that all Mersenne numbers with prime exponents are squarefree, it has also been conjectured that not all are squarefree. Guy, Unsolved Problems in Number Theory, Springer, 1994. For this reason I describe it as an "open question," rather than a conjecture. 

20051208, 04:01  #4 
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^p1, and a large lower bound they have tested up to. (Same thing for 7^p 1 and 11^p 1...etc...) 
20051212, 04:06  #5  
"William"
May 2003
Near Grandkid
5^{3}·19 Posts 
Quote:
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 20051212 at 04:09 

20051212, 04:31  #6 
Jun 2003
3137_{8} Posts 
You forgot 3^21 %(2^3)==0
Only solution to a^xb^y=1 Citrix 
20051212, 11:00  #7 
May 2003
60B_{16} Posts 
William,
Thanks. I found a paper by Peter Montgomery, giving the bounds I needed. Cheers, Pace 
20051212, 12:08  #8 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Which one is it?
Alex 
20051212, 18:02  #9 
May 2003
60B_{16} Posts 
It is called "New Solutions of , Mathematics of Computation, Vol. 61, No. 203, p. 361363.
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 20051212 at 23:49 Reason: added [tex] tags 
20051212, 21:37  #10  
Aug 2005
Brazil
2×181 Posts 
Quote:


20051212, 22:05  #11 
May 2003
7×13×17 Posts 
Ah, so that's how to do it. Last fiddled with by ZetaFlux on 20051212 at 22:06 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
square free Mersenne Numbers?  kurtulmehtap  Math  0  20120917 13:04 
Perfect square or not?  jnml  Puzzles  12  20120428 21:33 
red square  Fusion_power  Puzzles  14  20080425 11:37 
Find a Square  davar55  Puzzles  34  20070612 14:17 
Fast way to square???  maheshexp  Math  2  20040529 01:54 