Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I computed the factorization of $2^n-1$ for many $n$'s and came up with the following conjecture that for any odd prime $p$, $$ p^k || 2^n-1 \quad \Longleftrightarrow \quad O_p(2) p^{k-1} \, | \, n \quad with \quad p^{k-1} \, || \, n. $$ where $O_p(2)$ is the order of $2 \pmod p$. Here are my thoughts on the question.

We clearly need to assume $O_p(2) \, | \, n$ if $k \ge 1$, so the statement can be made easier to prove because we only need to show that by assuming this, $p^k \, | \, 2^n-1$ iff $p^{k-1} \, | \, n$. Let's prove $(\Longleftarrow)$ by induction. For $k = 1$ we have nothing to show. Say we take a general $k$, then by induction on $k$, $$ p^{k-1} \, | \, n \quad \Longrightarrow \quad 2^{p^{k-1} O_p(2)} - 1 = (2^{p^{k-2}O_p(2)})^p-1^p = (2^{p^{k-2}O_p(2)} - 1)(1 + 2^{p^{k-2}O_p(2)} + \dots + (2^{p^{k-2}O_p(2)})^{p-1} ) \equiv (p^{k-1}m)(\underset{p \text{ times}}{\underbrace{1 + \dots + 1}})\equiv 0 \pmod {p^k}. $$ So I've proved one direction. (Note that when $2$ is a primitive root $\pmod p$, this is actually quite trivial because my statement in the direction I proved it says 'since $\varphi(p^k) \, | \, n$, then $2^n \equiv 1 \pmod {p^k}$'.)

In the other direction the question seems quite hard though. For instance, if I just want to show this for $k = 2$, I need to prove that if $p^2 \, | \, 2^n-1$ then $p \, | \, n$. If I try to show that, then working modulo $p^2$ I get $$ 0 \equiv 2^n-1 = 2^{O_p(2) m} -1 = (2^{O_p(2)}-1)(1 + 2^{O_p(2)} + \dots + 2^{O_p(2)(m-1)}) \\\ \equiv (kp)(\underset{m \text{ times}}{\underbrace{1 + 1 + \dots + 1}} ) \equiv kpm \pmod {p^2} \\\ $$ and what I would need is to assume $p \, || \, 2^{O_p(2)}-1$, so that $p \, | \, m \, | \, n$... I think that if I have this the claim follows by induction, but I have absolutely no idea how to show this. I believe it is true though (computations).

Any ideas on this problem?

share|cite|improve this question
Please forgive my very naive question, but what does the double bar mean ? – Joel Cohen Jul 29 '12 at 12:16
The notation $p^k \mid \mid n$ usually means that $p^k$ is the exact power of $p$ dividing $n$. @JoelCohen – Bruno Joyal Jul 30 '12 at 17:51
@Joel Cohen : Yes, as Bruno said, the double bar notation is very standard for "exact division", in the sense that $p^k \, | \, n$ but $p^{k+1} \, \nmid \, n$. – Patrick Da Silva Jul 31 '12 at 1:43
You may be interested in this( – puresky Dec 14 '12 at 9:35

This happens to be false for $p=1093$, $k=1$ and $n=364 = O(2,1093)$. The conjecture breaks down because $2^{364} \equiv 1 \pmod {1093^2}$, i.e. the division on the LHS is not exact. I was stuck at proving the thing so I pushed Mathematica a little further to try some more number crunching and he popped out this counterexample...

share|cite|improve this answer
What about $p=3511$ (not had chance to look at it yet)? Are Wieferich primes relevant here? – Old John Jul 31 '12 at 8:29
@Old John : Yes, they are. I wanted to write about it but I was a little tired (and pissed) so I didn't. They are the two (known) counter examples to my conjecture. – Patrick Da Silva Jul 31 '12 at 17:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.