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?

  • 0
    Please forgive my very naive question, but what does the double bar mean ?2012-07-29
  • 1
    The notation $p^k \mid \mid n$ usually means that $p^k$ is the *exact* power of $p$ dividing $n$. @JoelCohen2012-07-30
  • 0
    @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$.2012-07-31
  • 1
    You may be interested in this(http://math.stackexchange.com/a/156614/12720).2012-12-14

1 Answers 1