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$ |
1 answer
+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)$.
0 comment threads
0 comment threads