# 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