Calculate the k in $b^k\equiv1(modM)$ Assume that b and M are both natural numbers and $b\lt M$. Can we find an integer, says k, that we can get $b^k\equiv 1\pmod M$? k is greater than $0$. If such a number does exist, what condition does it follow or how to calculate it? Thanks in advance!
 A: Suppose that $\gcd(b,M)\gt 1$. Then there cannot be such a $k$. So we suppose that $\gcd(b,M)=1$.
Consider the numbers $b^1,b^2,b^3, b^4,\dots, b^M$. These are all relatively prime to $M$. Imagine computing their remainders on division by $M$. We have $M$  numbers, and at most $M-1$ conceivable remainders. 
Thus there exist integers $m$ and $n$, with $1\le m\lt n\le M$ such that $b^m$ and $b^n$ have the same remainder on division by $M$, and therefore $b^m\equiv b^n\pmod{M}$. It follows that $b^{n-m}\equiv 1\pmod{M}$. 
Remark: For very large $M$ it can be difficult to compute suitable $k$. Even when we have found one, it is not easy to find the smallest one.
A: Assuming that the solution exists, to calculate $k$ is a very hard question if your $M$ is big. If your $M$ is small, the best and easist way to do it is by naively computing $b^k$ for all $k$ from $1$ to $M$ and checking if you have $b^k\equiv 1$.
If your $M$ is a big number, there are many algorithms that you can call upon, such as the Baby-step Giant-step, Silver--Pohlig--Hellman algorithm, the index calculus  etc. If your $M$ is really big, the state of the art method is the Number Field Sieve for Discrete Logarithm Problem.
