Multiplicative order of 2 mod 2n+1

The question

conjecture1. If $p$ is an odd prime then $a((p^3-1)/2)=p\cdot a((p^2-1)/2)$. Because otherwise $a((p^3-1)/2)<p\cdot a((p^2-1)/2)$ iff $a((p^3-1)/2)=a((p-1)/2)$ for a prime $p$. Equivalently $p^3$ divides $2^{p-1}-1$, but no such prime $p$ is known.

• Thomas Ordowski, Feb 10 2014

conjecture2. A generalization of the previous conjecture: For each $k\ge 2$, if $p$ is an odd prime then $a((p^{k+1}-1)/2)=p\cdot a((p^k-1)/2)$. Computer testing of this generalized conjecture shows that there is no counterexample for $k$ and $p$ both up to 1000.

• Ahmad J. Masad, Oct 17 2020

The two are in fact equivalent. Its $k=2$ instance is conjecture1. Conversely, write $d={\mathrm{ord}}_{p^2}(2)$. conjecture1 for $p$ says $v_p(2^d-1)=2$, and lifting the exponent for the odd prime $p$ then gives $v_p(2^{d{p}^t}-1)=2+t$, hence ${\mathrm{ord}}_{p^{2+t}}(2)=d{p}^t$ for every $t\ge 0$, which is every instance for that $p$.

The multiplicative order of 2 modulo $2n+1$. In other words, the least $m>0$ such that $2n+1$ divides $2^m-1$.

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.OEIS.«2326» (2 statements).

theorem conjecture1 (p : ℕ) (hp : p.Prime) (hp_odd : p ≠ 2) :
    a ((p ^ 3 - 1) / 2) = p * a ((p ^ 2 - 1) / 2)

theorem conjecture2 (k : ℕ) (hk : 2 ≤ k) (p : ℕ) (hp : p.Prime) (hp_odd : p ≠ 2) :
    a ((p ^ (k + 1) - 1) / 2) = p * a ((p ^ k - 1) / 2)

What counts as progress

• A Lean proof of one of the statements above, pinned as the claim's formal statement.
• Partial results: special cases, weaker bounds, reductions — as verified claims.
• Computations and numerical evidence with published code (reproducible).
• Literature: the problem may have been solved or partly solved already. Report it as a literature claim.
• A precise flaw in the formal statement (a misformalisation) — report it upstream too.

References

• A002326

Source and licence

Imported from Formal Conjectures (OEIS), commit e6d1743831c2. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.