Solving Diophantine Equation $xB=(2^N)-1$

Question

If given a value for $x$, does anyone have a way to solve the diophantine equation below?

$xB=(2^N)-1$

where $x,B,N\in\mathbb Z$

Where presumably a smaller $N$ is better, but any way to find a value of $N$ (and $B$) is a good solution.

All i can think of is brute force unfortunately... trying ever increasing values of $N$ to see if $(2^N)-1$ is a perfect multiple of $x$

Answer 1

So, given $x$, we have to find minimum $N$ and $B$, so that $$ x\,B = 2^{\,N} - 1\quad \Rightarrow \quad x,B\;{\rm odd} $$ I can provide just some preliminary considerations. Let represent all three parameters in binary base. Take $x$ to be: $$ x = {\rm odd} = 1\;b\; \cdots \;b\,\;1_2 \;(m\;{\rm bits}) < 2^{\,m} $$

Then we must have: $$ x\,B\, = 2^{\,N} - 1 = 1\;\,1\,\; \cdots \;\,1_2 $$ Since binary multiplication translates into the sum of shifted $x$ strings, then the identity above means :
start with $x*1$ , then add a $x$-string shifted so that its LSB=$1$ fits with the first $0$, compute the sum, continue with next $0$.
So the question becomes for which values of $x$ this iteration terminates, and we know there are some.

If $N$ satisfies the identity, then the next following multiple of it shall be $$ q\;:\quad 2^{\,M} - 1 = q\left( {2^{\,N} - 1} \right) $$ Since we have $$ {{2^{\,M} - 1} \over {2 - 1}} = \sum\limits_{0\, \le \,k\, \le \,M - 1} {2^{\,k} } = \sum\limits_{0\, \le \,k\, \le \,N - 1} {2^{\,k} } + 2^{\,N} \sum\limits_{0\, \le \,k\, \le \,M - N - 1} {2^{\,k} } $$

Thus the minimum $q$ will be $$ 2^{\,2N} - 1 = \left( {2^{\,N} + 1} \right)\left( {2^{\,N} - 1} \right)\quad \Rightarrow \quad \min \;q = \left( {2^{\,N} + 1} \right) $$ and thus either there is no solution or there are infinite.
(added)
We deduce that a solution exists for all the $x$ that have a periodic binary representation, where the number of consecutive $1$s is congruent with the number of consecutive $0$s.
Example:
$x = 1\,1\;0\;0\;0\;0\;1\;1_{\,2} = 195$
$B = 1\,0\;1\;0\;1_{\,2} = 21$
$x\,B = 4095 = 2^{\,12} - 1$

Answer 2

I presume you mean the positive integers, not $\mathbb Z$, else you could take $B=N=0$. You want the least positive $N$ such that $2^N \equiv 1 \mod x$. If $x$ is even, this is impossible, else it is the order of $2$ in the multiplicative group of units of $\mathbb Z/x\mathbb Z$. Start with Euler's theorem. If you can factor $\phi(x)$ it's easy.

Answer 3

Here are the first few instances of $N$, $2^N-1$ and the latter's prime factors:

1 -> 1: []
2 -> 3: [[3, 1]]
3 -> 7: [[7, 1]]
4 -> 15: [[3, 1], [5, 1]]
5 -> 31: [[31, 1]]
6 -> 63: [[3, 2], [7, 1]]
7 -> 127: [[127, 1]]
8 -> 255: [[3, 1], [5, 1], [17, 1]]
9 -> 511: [[7, 1], [73, 1]]
10 -> 1023: [[3, 1], [11, 1], [31, 1]]
11 -> 2047: [[23, 1], [89, 1]]
12 -> 4095: [[3, 2], [5, 1], [7, 1], [13, 1]]
13 -> 8191: [[8191, 1]]
14 -> 16383: [[3, 1], [43, 1], [127, 1]]
15 -> 32767: [[7, 1], [31, 1], [151, 1]]
16 -> 65535: [[3, 1], [5, 1], [17, 1], [257, 1]]
17 -> 131071: [[131071, 1]]
18 -> 262143: [[3, 3], [7, 1], [19, 1], [73, 1]]
19 -> 524287: [[524287, 1]]
20 -> 1048575: [[3, 1], [5, 2], [11, 1], [31, 1], [41, 1]]
21 -> 2097151: [[7, 2], [127, 1], [337, 1]]
22 -> 4194303: [[3, 1], [23, 1], [89, 1], [683, 1]]
23 -> 8388607: [[47, 1], [178481, 1]]
24 -> 16777215: [[3, 2], [5, 1], [7, 1], [13, 1], [17, 1], [241, 1]]
25 -> 33554431: [[31, 1], [601, 1], [1801, 1]]
26 -> 67108863: [[3, 1], [2731, 1], [8191, 1]]
27 -> 134217727: [[7, 1], [73, 1], [262657, 1]]
28 -> 268435455: [[3, 1], [5, 1], [29, 1], [43, 1], [113, 1], [127, 1]]
29 -> 536870911: [[233, 1], [1103, 1], [2089, 1]]
30 -> 1073741823: [[3, 2], [7, 1], [11, 1], [31, 1], [151, 1], [331, 1]]
31 -> 2147483647: [[2147483647, 1]]

Hm, aren't these Mersenne primes?

32 -> 4294967295: [[3, 1], [5, 1], [17, 1], [257, 1], [65537, 1]]
33 -> 8589934591: [[7, 1], [23, 1], [89, 1], [599479, 1]]
34 -> 17179869183: [[3, 1], [43691, 1], [131071, 1]]
35 -> 34359738367: [[31, 1], [71, 1], [127, 1], [122921, 1]]
36 -> 68719476735: [[3, 3], [5, 1], [7, 1], [13, 1], [19, 1], [37, 1], [73, 1], [109, 1]]
37 -> 137438953471: [[223, 1], [616318177, 1]]
38 -> 274877906943: [[3, 1], [174763, 1], [524287, 1]]
39 -> 549755813887: [[7, 1], [79, 1], [8191, 1], [121369, 1]]
40 -> 1099511627775: [[3, 1], [5, 2], [11, 1], [17, 1], [31, 1], [41,1], [61681, 1]]
41 -> 2199023255551: [[13367, 1], [164511353, 1]]
42 -> 4398046511103: [[3, 2], [7, 2], [43, 1], [127, 1], [337, 1], [5419, 1]]
43 -> 8796093022207: [[431, 1], [9719, 1], [2099863, 1]]
44 -> 17592186044415: [[3, 1], [5, 1], [23, 1], [89, 1], [397, 1], [683, 1], [2113, 1]]
45 -> 35184372088831: [[7, 1], [31, 1], [73, 1], [151, 1], [631, 1], [23311, 1]]
46 -> 70368744177663: [[3, 1], [47, 1], [178481, 1], [2796203, 1]]
47 -> 140737488355327: [[2351, 1], [4513, 1], [13264529, 1]]
48 -> 281474976710655: [[3, 2], [5, 1], [7, 1], [13, 1], [17, 1], [97, 1], [241,1], [257, 1],
[673, 1]]
49 -> 562949953421311: [[127, 1], [4432676798593, 1]]
50 -> 1125899906842623: [[3, 1], [11, 1], [31, 1], [251, 1], [601, 1], [1801, 1], [4051, 1]]
51 -> 2251799813685247: [[7, 1], [103, 1], [2143, 1], [11119, 1], [131071, 1]]
52 -> 4503599627370495: [[3, 1], [5, 1], [53, 1], [157, 1], [1613, 1], [2731, 1], [8191, 1]]
53 -> 9007199254740991: [[6361, 1], [69431, 1], [20394401, 1]]
54 -> 18014398509481983: [[3, 4], [7, 1], [19, 1], [73, 1], [87211, 1], [262657, 1]]
55 -> 36028797018963967: [[23, 1], [31, 1], [89, 1], [881, 1], [3191, 1], [201961, 1]]
56 -> 72057594037927935: [[3, 1], [5, 1], [17, 1], [29, 1], [43, 1], [113, 1], [
127, 1], [15790321, 1]]
57 -> 144115188075855871: [[7, 1], [32377, 1], [524287, 1], [1212847, 1]]
58 -> 288230376151711743: [[3, 1], [59, 1], [233, 1], [1103, 1], [2089, 1], [303
3169, 1]]
59 -> 576460752303423487: [[179951, 1], [3203431780337, 1]]

My machine slows down here:

60 -> 1152921504606846975: [[3, 2], [5, 2], [7, 1], [11, 1], [13,1],
[31, 1], [41, 1], [61, 1], [151, 1], [331, 1], [1321, 1]]
61 -> 2305843009213693951: [[2305843009213693951, 1]]

Looks like there are not too many solutions in reach.