Replacing mod in equation I'm trying to find the smallest integer $x$ such that $2^x \equiv 166 \pmod {330}$. It is result of a problem I am solving and I am wondering is there a way to find suitable $x$ without trying all possible values?
I've noticed that $x=20$ works.
Even some algorithm (it is part of the programming task and there will be way bigger numbers given) which would reduce at least the values I have to try somehow (not go from 1 up to 20).
 A: Whenever you have $a^x\equiv b\pmod{n}$ it all depends whether $n$ is prime or composed.
In case $n$ is composed you can reduce the problem by using little Fermat theorem.
e.g. if $n=pq$ then you get the system
$\begin{cases}
a^{x}\pmod{p}\equiv(a\pmod{p})^{x\pmod{p-1}}\pmod{p}\equiv {a_1}^{x_1}\pmod{p}\\
a^{x}\pmod{q}\equiv(a\pmod{q})^{x\pmod{q-1}}\pmod{q}\equiv {a_2}^{x_2}\pmod{q}\end{cases}$
In our case, since $2$ is small already, $a=a_1=a_2=2$ do not change, but since $p,q$ are smaller you get less tries to perform to search for $x_1$ and $x_2$.
Once you get them, you can apply LCM or CRT to get $x$.
Unfortunately for prime numbers $p$, you cannot reduce further and if they are large, then you get to try all values.
There are however algorithms like baby-step giant-step to achieve discrete logarithm, but these are not easy and straightforward:
https://en.wikipedia.org/wiki/Discrete_logarithm
A: Write $330 = 2 \cdot 3 \cdot 5 \cdot 11$.
Then
$2^x \equiv 330/2 + 1 \bmod 330$ iff $2^x \equiv 0 \bmod 2 $ and $2^x \equiv 1 \bmod p $ for $p=3,5,11$.
The order of $2$ mod $3$ is $2$.
The order of $2$ mod $5$ is $4$.
The order of $2$ mod $11$ is $10$.
Therefore, $x$ is a multiple of $lcm(2,4,10)=20$.
