6
$\begingroup$

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?

  • 1
    You may be interested in this(http://math.stackexchange.com/a/156614/12720).2012-12-14

1 Answers 1

3

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

  • 0
    @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.2012-07-31