# 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).

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

• I am not sure if I follow correctly. If you would not mind checking my steps on next example: 2^x = 2704 mod 5406 5406 -> 2 * 3 * 17 * 53 (p = 102; n = 53 for example) $\begin{cases} 2^{x}\pmod{102}\equiv(2\pmod{102})^{x\pmod{101}}\pmod{102}\equiv 1\\ 2^{x}\pmod{53}\equiv(2\pmod{53})^{x\pmod{52}}\pmod{53}\equiv 8\\ 2^{x1}\pmod{102}\equiv 1\\ 2^{x2}\pmod{53}\equiv 8\\\end{cases}$ 102 is not prime so I recursively continue solving? And stop for 53 since its prime? So I get basically equation for each prime in n and solve each one and find LCM for those numbers? – eXPRESS Dec 25 '18 at 14:01
• Yes, this is it. I admit that generally we use this when $x$ is known, as for solving this kind of problem math.stackexchange.com/questions/3042801/… but it could be also used for equations. Here $53$ is quite smaller compared to $5406$ so $x_2$ is easier to find. If the $a_i$ are constant the lcm works fine, but if not, it is a little more complicated to find the correct power back, you have to use CRT with $(p_i-1)$ mods. – zwim Dec 25 '18 at 19:37
• See en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm for a complete description in most general case. My method is just a simplified version. – zwim Dec 25 '18 at 19:48
• Thanks for confirmation/information and further materials. :) – eXPRESS Dec 27 '18 at 19:30

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$$.

• Thank you very much, but if I see correctly it yields n! options where n is count of numbers in LCM right? Hopefully that is gonna be enough for the huge numbers I will be given. :) – eXPRESS Dec 25 '18 at 11:06