Post History

Finding the smallest Mersenne-number multiple of an odd integer

### 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$ |