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?

$\endgroup$
4
  • $\begingroup$ Please forgive my very naive question, but what does the double bar mean ? $\endgroup$
    – Joel Cohen
    Jul 29, 2012 at 12:16
  • 1
    $\begingroup$ The notation $p^k \mid \mid n$ usually means that $p^k$ is the exact power of $p$ dividing $n$. @JoelCohen $\endgroup$
    – Bruno Joyal
    Jul 30, 2012 at 17:51
  • $\begingroup$ @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$. $\endgroup$
    – Patrick Da Silva
    Jul 31, 2012 at 1:43
  • 1
    $\begingroup$ You may be interested in this(math.stackexchange.com/a/156614/12720). $\endgroup$
    – puresky
    Dec 14, 2012 at 9:35

1 Answer 1

Reset to default
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ What about $p=3511$ (not had chance to look at it yet)? Are Wieferich primes relevant here? $\endgroup$
    – Old John
    Jul 31, 2012 at 8:29
  • $\begingroup$ @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. $\endgroup$
    – Patrick Da Silva
    Jul 31, 2012 at 17:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .