0
$\begingroup$

Suppose $a$ and $b$ are relatively prime integers $\geq 2$. I need to find the smallest positive integer $n$ such that $b^n-1$ is divisible by $a$. Is there an efficient algorithm for finding this, or do I need to use brute force?

I looked into this a bit and the answer seems related to Euler's totient function, but the only thing I've found so far is that if $m$ (the answer I'm looking for) is the smallest such $n$, then $m \leq \phi(a)$; I didn't find anything that would tell me how I could tell when $m = \phi(a)$ or if there were any other way to narrow down the possibilities so that I wouldn't have to check every number from $1$ to $\phi(a)$.

$\endgroup$
1
$\begingroup$

Essentially, you're looking for the smallest $n$ such that $b^n \equiv 1 \pmod a$. This is called the "order" of $b$.

First: let $k$ be any integer, not necessarily the smallest one, such that $b^k \equiv 1 \pmod a$. Can you show that $m$ divides $k$?

Second: there are many ways of showing that $b^{\varphi(a)} \equiv 1 \mod a$. (Euler's theorem)

What does this imply about your $m$?

$\endgroup$
  • $\begingroup$ Thanks, I didn't know it was called "order". (Or "multiplicative order".) That will help me look into it myself further, to see what efficient algorithms there might be for computing it. So $m$ divides $\varphi(a)$, which should help even if I can't find any other info. $\endgroup$ – ajb Sep 24 '14 at 17:14

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.