Minimal integer to make a rational into an integer

Question

Let $q = \frac ab$ be any rational number such that $a < b$. What is the smallest positive integer $n$ such that $\frac ab \times \left(2^n-1\right)$ is an integer?

Answer 1

It's simply the binary analog of computing the decimal period of a fraction.

W.l.o.g. generality we may assume that $\,a/b\,$ is reduced, i.e. $\,d = \gcd(a,b) = 1\ $ (else cancel $d).$

Then $\, (2^{\large n}-1)a/b = k\in\Bbb Z\iff bk = (2^{\large n}-1)a\ $ so $\,b\mid a(2^{\large n}-1).\,$ Since $\,\gcd(b,a) = 1\,$ we infer by Euclid's Lemma that $\,b\mid 2^{\large n}-1,\,$ i.e. $\,2^{\large n}\equiv 1\pmod{\!b}.\,$

Since $\,2^{\large n}-1\,$ is odd its factor $b$ must be odd, and it is easy to show that such an $n$ must exist, e.g. by a pigeonhole argument, or by Euler's phi theorem (or Lagrange) we can choose $\,n = \phi(b).$

The least such $\,n > 0\,$ is known as the order of $\,2\,$ modulo $\,b.\,$ It can be verified using the Order Test and computed by various algorithms.