# Minimal integer to make a rational into an integer

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?

• By definition, that the order of $2$ $\pmod b$. Note that if $b$ is even, then there is no such $n$. – lulu Jun 16 at 13:37
• If $a,b$ have no common divisor, then search for the smallest $n$ s.t. $b$ divides $2^n-1$. – Wuestenfux Jun 16 at 13:40
• There is no easy way to compute $n$, unfortunately. General theory tells us that $n$ is a divisor of $\varphi(b)$, where $\varphi$ denotes Euler's totient function In particular, $\varphi(b)$ always works as an exponent $n$, but it won't, in general, be minimal. – lulu Jun 16 at 13:48
• @Sim But it seemed you were by calling the question's raison d'etre a "small tangent" . That's why I was puzzled by your remark. – Bill Dubuque Jun 16 at 15:26
• @SimplyBeautifulArt and Bill Dubuque, thanks for the responses---I used the "binary" tag when posting the question for the same connection identified in Bill's answer. – jII Jun 16 at 16:42

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.