Unable to solve this exponential equation - Diffie-Hellman key exchange

Question

By looking at it, I can deduce that $a = 6$, and $b = 5$, but how do I can solve for $a$ and $b$ without guessing?

$$2^a = 11b + 9$$

Answer 1

Write $$2^a\equiv9\pmod{11}.$$ Rewrite it as $$2^a\equiv-2\pmod{11},$$or $$2^{a-1}\equiv-1\pmod{11}.$$ Squaring both sides, $$2^{2a-2}\equiv1\pmod{11}.$$ By Fermat's little theorem, we know that one solution is $$2a-2=10\iff a=6$$ Any smaller exponent must be must be a factor of $10$, and the only even factor of $10$ is $2,$ but $2a-2=2$ gives $a=2,$ which doesn't give a solution.

Since $2^{10}\equiv 1\pmod{11},$ all values of the form $a=10k+6$ actually lead to solutions.

As has been pointed out in the comments, this is a discrete logarithm problem, and is very difficult in general. Usually the problem is to find the smallest exponent that would work, which involves find the factors of the exponent that you get from little Fermat. Since factoring is very difficult, so is this problem.

Answer 2

This equation in a way can be related to Collatz conjecture. There is a set of infinite odd numbers which satisfy the condition of Collatz conjecture; this set is:

$K=\{1,5,21,85,341,1365,5461,21845 . . .(4k_{i-1}+1)\}$; $i ∈ N$

So that:

$3\times k_i+1=2^n$

Which due to Collatz conjecture leads to 1 by cintinious dividing by 2.

Hence the equation can also be written as:

$11a+9=3k+1$; $k ∈ K$

The general solutions of this equation are:

$a=4t+5$

$k=11t+21$

Where 5 and 21 are a solution of equation. We can see that is set K, in addition to $k_3=21$ which gives $a=5$ and $n=6$ there is another numbers such as $k_8=21845$ which gives $n=16$ and $a=5957$:

$3\times21845+1=65536=2^{16}$

$65536=5957\times 11+9$

which sre resulted with $t=1488$.

It is not known the number of solutions of this equation is infinite, however using general solution and try more numbers for t we may find even more solutions by Brut force.