Q&A

# Finding the smallest Mersenne-number multiple of an odd integer

+5
−0

### Problem

Given an odd integer $a$, there exists some smallest $b$ such that $a\times b = 2^n-1$ (for some $n$). Find $b$ and $n$.

• What is an upper bound for this problem?
• What is a lower bound for this problem?
• In what cases is it easier?

## Naïve algorithm

I know I can count up all $n$ from $\lceil \log_2 a \rceil$ until I find $2^n-1 = 0 \mod a$:

assert is_odd(a)
for n := ceil(log₂(a)) to infinity:
b := ((2^n)-1) / a
if is_integer(b):
return b, n


If $n < a$ (which might be true), my naïve algorithm is $O(n)$.

## Table

$a$ $b$ $n$
$1$ $1$ $1$
$3$ $1$ $2$
$5$ $3$ $4$
$7$ $1$ $3$
$11$ $93$ $10$
$13$ $315$ $12$
$15$ $1$ $4$
$17$ $15$ $8$
$19$ $13797$ $18$
$21$ $3$ $6$
$23$ $89$ $11$
$25$ $41943$ $20$
$27$ $9709$ $18$
$29$ $9256395$ $28$
$31$ $1$ $5$
$33$ $31$ $10$
Why does this post require moderator attention?
Why should this post be closed?

+1
−0

Add one to both sides and consider residues modulo $a$ to get $$2^n \equiv 1 \pmod a$$

So you want to find the multiplicative order of $2$ modulo $a$. As you note, $2^n \ge a + 1$ so $n \ge \lg(a+1)$; by Lagrange's theorem, $n \le \varphi(a)$, where $\varphi$ is Euler's totient function. More generally, $n$ is a factor of $\varphi(a)$, so it's easier when you know the factorisation of $\varphi(a)$.

Why does this post require moderator attention?