# Statement about the order of $2$ modulo prime powers

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?

-
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(math.stackexchange.com/a/156614/12720). –  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...
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