1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ By definition, that the order of $2$ $ \pmod b$. Note that if $b$ is even, then there is no such $n$. $\endgroup$ – lulu Jun 16 at 13:37
  • 1
    $\begingroup$ If $a,b$ have no common divisor, then search for the smallest $n$ s.t. $b$ divides $2^n-1$. $\endgroup$ – Wuestenfux Jun 16 at 13:40
  • 1
    $\begingroup$ 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. $\endgroup$ – lulu Jun 16 at 13:48
  • 1
    $\begingroup$ @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. $\endgroup$ – Bill Dubuque Jun 16 at 15:26
  • 2
    $\begingroup$ @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. $\endgroup$ – jII Jun 16 at 16:42
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.