# Math Help - Mersenne numbers

1. ## Wiki

According to Wiki (Wieferich prime - Wikipedia, the free encyclopedia), for a Mersenne number M_q, if there exists a p^2|M_q where p and q are relatively prime, then p is a Wieferich prime. This result does not seem trivial to me, and it is uncredited, so I wonder if it is correct. It is equivalent to saying that not only are Wieferich primes counterexamples to your conjecture, but they are the only counterexamples. If this is correct, then you can prove there are only finite Wieferich numbers by placing a lower bound on your conjecture.

2. Originally Posted by Media_Man
According to Wiki (Wieferich prime - Wikipedia, the free encyclopedia), for a Mersenne number M_q, if there exists a p^2|M_q where p and q are relatively prime, then p is a Wieferich prime. This result does not seem trivial to me, and it is uncredited, so I wonder if it is correct.
This part of the theorem is true for sure. If p^2|M_q then q| p-1, which implies that
2^q - 1|2^(p-1) - 1, from which p^2|2^(p-1) - 1 follows. The reverse direction of that theorem (recall that the theorem is 'iff') is not at all obvious to me.

Originally Posted by Media_Man
It is equivalent to saying that not only are Wieferich primes counterexamples to your conjecture, but they are the only counterexamples. If this is correct, then you can prove there are only finite Wieferich numbers by placing a lower bound on your conjecture.
I'm not sure I follow you here. Can you explain? Remember that in my conjecture, the integer n in 2^n -1 can be composite, whereas in theorem quoted on wiki, n is a prime.

3. Actually that theorem on wiki is flawed (see link 5 at bottom of page and scroll down to the conjecture about square factor of M_q).

Indeed it is an open problem whether or not there are any Mersenne numbers (with prime index) that posses square factors. The two currently known Wieferich primes don't work.

4. ## All Jamix primes are Wieferich primes

Here are four lemmas I have been able to prove. I am not well versed enough in number theory to know which are obvious or already known. Let me know and I can provide proofs for any or all of them:

Let $p$ be an odd prime and define $r$ as the lowest positive integer satisfying $2^r \equiv 1 (\bmod p)$. Denote $M_n$ as the nth Mersenne $2^n-1$. Then the following hold:

(1) if $M_a \equiv M_b (\bmod n)$ then $M_{ka} \equiv M_{kb} (\bmod n)$ for any $a,b,n,k$
(2) $r|p-1$
(3) if $p|M_n$ then $r|n$
(4) $M_{kr} \equiv kM_r (\bmod p^2)$ for all $k$

Theorem: If $p^2|2^n-1$ for some odd prime $p$ and positive integer $n$, then $p|n$ or $p$ is a Wieferich prime.

Proof: Let $p^2|2^n-1$ for some odd prime $p$ and positive integer $n$. By (3), $p^2|2^{kr}-1$ for some positive int $k$. By (4), $p^2|k(2^r-1)$. Since $p|2^r-1$ by definition of $r$, then $p|k$ or $p^2|2^r-1$. If $p|k$ then $p|n$. By (1) and (2), if $p^2|2^r-1$ then $p^2|2^{p-1}-1$. Therefore, either $p|n$ or $p$ is a Wieferich prime.

Note: I have verified this numerically up to $n=10,000$. The only counterexamples I found to your original conjecture were the two known Wieferich primes, 1093 and 3511. I thought this was odd since your conjecture did not seem as strong as the Wieferich condition. But the above proof does indeed verify it. If $p^2|2^n-1$ for some $p \not | \ n$ (a Jamix prime), then $p$ is a Wieferich. So $p$ is a Jamix prime iff $p$ is a Wieferich prime. Short-lived legacy - sorry.

So, pick your favorite large integer $L>3511$, and if you can show that for any $p$, your conjecture holds for all $n>L$, that would mean there are no counterexamples $>L$, i.e. no Wieferich primes $>L$. (It is an open question whether there are a finite number of them or infinite. If there are any other Wieferich primes besides 1093 and 3511, they must be greater than $10^{25}$ or something ridiculous like that.)

Fermat's Little Theorem tells us that $p|2^{p-1}-1$ for all odd primes $p$. By (2), for some primes $p$ there exists an $r where $r|p-1$ satisfying $p|2^r-1$, but for some primes there does not. A question I am interested in is why this $r exists only some of the time? For which primes does $r$ not exist? Are there only a finite number of either case?

5. Could you prove (4)? I think this might be a result of Abel but I don't I have time to check (I've got a stat exam in a couple of hours so I'm mostly online to review lecture notes).

6. ## A tedious and tree-killing proof

For some odd prime $p$, define $r$ as the lowest positive int satisfying $2^r \equiv 1 (\bmod p)$

Lemma (4) $M_{kr} \equiv kM_r (\bmod p^2)$

Proof: $2^r \equiv 1 (\bmod p)$ by definition.
So $2^r \equiv sp+1 (\bmod p^2)$ for some positive int $s$
Thus, $2^{kr} \equiv (sp+1)^k (\bmod p^2)$
Expanding by the binomial theorem, $(sp+1)^k=p^2(...)+sp+1$
So $2^{kr} \equiv sp+1 (\bmod p^2)$
Now, $2^{kr}(2^r-1) \equiv (sp+1)sp (\bmod p^2)$
Multiplying, $2^{kr}(2^r-1) \equiv (s^2p^2+sp) (\bmod p^2)$
So $2^{kr}(2^r-1) \equiv sp (\bmod p^2)$
So $2^{kr}(2^r-1) \equiv 2^r-1 (\bmod p^2)$
Distribute $2^{(k+1)r}-2^{kr} \equiv 2^r-1 (\bmod p^2)$
Now $2^{(k+1)r}-1-(2^{kr}-1) \equiv 2^r-1 (\bmod p^2)$
Giving us $M_{(k+1)r}-M_{kr}\equiv M_r (\bmod p^2)$
So $M_{(k+2)r}-M_{kr} = M_{(k+2)r}-M_{(k+1)r}+M_{(k+1)r}-M_{kr} = M_r+M_r = 2M_r (\bmod p^2)$
We can generalize this to $M_{(k+a)r}-M_{kr} = aM_r (\bmod p^2)$
Letting $k=0, M_{ar}-M_0 = aM_r (\bmod p^2)$
Noting that $M_0=2^0-1=1-1=0$, $M_{ar} = aM_r (\bmod p^2)$

I'm sure there's a less tedious way of doing this, but as you can see, some fancy and admittedly liberal manipulation of modular arithmetic gets it done. A peculiar property of $r$ (the "order" of 2, mod p, I believe) and Mersenne numbers.

Note: If $s=0$ in the above construction, then $p$ is a Wieferich prime. Looking at these on a computer, $s$ appears to be pretty random, as does $r$. This leads me to wonder if they are computable at all. My guess is no.

7. I was able to verify the theorem you put (there are a couple of well known tricks that make the proof very simple). If you don't mind though, let me nitpick through yours.

Originally Posted by Media_Man
Theorem: If $p^2|2^n-1$ for some odd prime $p$ and positive integer $n$, then $p|n$ or $p$ is a Wieferich prime.

Proof: Let $p^2|2^n-1$ for some odd prime $p$ and positive integer $n$. By (3), $p^2|2^{kr}-1$ for some positive int $k$
How does this follow from (3)? Did you mean (1) or (2) instead?

Originally Posted by Media_Man
For some odd prime $p$, define $r$ as the lowest positive int satisfying $2^r \equiv 1 (\bmod p)$

Lemma (4) $M_{kr} \equiv kM_r (\bmod p^2)$

Proof: $2^r \equiv 1 (\bmod p)$ by definition.
So $2^r \equiv sp+1 (\bmod p^2)$ for some positive int $s$
Thus, $2^{kr} \equiv (sp+1)^k (\bmod p^2)$
Expanding by the binomial theorem, $(sp+1)^k=p^2(...)+sp+1$

I got up to here in your proof to (4). We have that $(sp+1)^k=p^2(...)+ksp+1$ by expanding though.

Are you familiar with Euler's famous theorem (seehttp://en.wikipedia.org/wiki/Euler%27s_theorem otherwise)? Here is a proof using this and one other trick.

Proof: We know that $p^2|2^{p(p-1)}-1$ by Euler's theorem. As $p^2|2^{n}-1$, it follows that (this is the other trick!) the order of 2 must divide $gcd(n,p*(p-1))$. If gcd(n,p)=1, then $gcd(n,p*(p-1)) = gcd(n,p-1)$. As $gcd(n,p-1)|p-1$, it follows that $p^2|2^{p-1}-1$ making it a Wieferich number.

Originally Posted by Media_Man
Fermat's Little Theorem tells us that $p|2^{p-1}-1$ for all odd primes $p$. By (2), for some primes $p$ there exists an $r where $r|p-1$ satisfying $p|2^r-1$, but for some primes there does not. A question I am interested in is why this $r exists only some of the time? For which primes does $r$ not exist? Are there only a finite number of either case?
r is called the order of 2. If r=p-1, then we say that 2 is primitive with respect to p. The questions your asking are well known, however I don't think they have all been solved. I believe (but I'm not sure) that it is still an open question whether or not there are infinitely many primes p such that 2 is primitive.

8. Media_Man and Aryth

If you guy don't mind, I'd like to write up a 1-2 page paper of the theorem recently posted by Media_Man, with you guys as coauthors. I don't know if it will necessarily be accepted, but I'll ask my supervisor on Monday which Journal would be most optimal to send a short result like this to. So long as its new (which I'm still not sure of), I think its worth a shot. Let me know what you guys think.

9. ## My mistake...

I got up to here in your proof to (4). We have that $(sp+1)^k=p^2(...)+ksp+1$ by expanding though.
Yes, that is correct, that is my mistake. The proof still holds, though, as three lines later, the $ksp$ term would become $ks^2p^2$ and would still disappear via the modulus of $p^2$. Good catch.

By (3), $p^2|2^{kr}-1$ for some positive int k
(3) actually follows from (1) and (2), via Fermat's Little Theorem. Since $p^2|2^n-1$ , then $p|2^n-1$ , so by (3) $r|n$ .

Proof: We know that $p^2|2^{p(p-1)}-1$ by Euler's theorem. As $p^2|2^{n}-1$, it follows that (this is the other trick!) the order of 2 must divide $gcd(n,p*(p-1))$. If $gcd(n,p)=1$, then $gcd(n,p*(p-1)) = gcd(n,p-1)$. As $gcd(n,p-1)|p-1$, it follows that $p^2|2^{p-1}-1$ making it a Wieferich number.
Much more succinct. I figured as such.

If you guy don't mind, I'd like to write up a 1-2 page paper of the theorem recently posted by Media_Man, with you guys as coauthors.
Sounds good. Although the above proof derived from Euler gives a very nice shortcut to all the crap I went through. The major result here is that the Wieferich primes are the only counterexamples to Jamix's original conjecture that $p|2^n-1$ implies $p|n$ . This gives us another angle of defining Wieferich primes that may (or may not) aid in proving how many there are.

10. Thats great. I sent Aryth a pm to ask him as well. I'll write this up soon and post a first draft here for you (and hopefully Aryth) to comment on soon.

11. Hey guys,

sorry to say, but that small result which I thought was new turns out actually to not be new (look at the bottom paragraph here: Wieferich Prime -- from Wolfram MathWorld). Oh well.

12. I knew that it was older material. There are conjectures on the Wieferich primes dating back to 1910. I've done my fair share of research on them, they seem to have interesting properties, but alas, hardly anything about the Wieferich primes is unknown.

Page 2 of 2 First 12