A simple congruent equation $3^a\equiv1+b\mod m$

Question

I come across a simple congruent equation as follows: let $m\geq 10$ be an integer.It is not a power of $3$. Then how can we find some $a$ and $b$ (they are integers) such that $$3^a\equiv1+b\pmod{m},$$ where $b$ satisfies the condition:$\frac{m}3<b<\frac{2m}3.$

Answer 1

Here's a particular case where we can guarantee an answer.

Take $m>3$, $m\equiv 1 \pmod 3$. Let $n = \mathrm{ord}_m(3)$, so $3^n\equiv 1 \pmod m$. This means that $3^n = mk+1$ for some $k \equiv 2 \pmod 3$.

Since $k = 3l+2$ then $3^{n}= mk+1 = 3lm+2m+1$, so

$$3^{n-1}-1 = lm+\frac{2m-2}{3}$$

Reducing modulo $m$ we have

$$(3^{n-1}-1) \bmod m = \frac{2m-2}{3}$$ and

$$\frac{m}{3}<\frac{2m-2}{3}<\frac{2m}{3}$$

So in this case there's a solution $a = n-1$.

Answer 2

Since we can solve for $b$, it is superfluous, so we may just simply ask if there exists $a$ such that $\frac{m}{3} < (3^a-1) \bmod m < \frac{2m}{3}$.

I think it should be relatively easy to prove that there is a solution if $3$ is a primitive root modulo $m$. But no simple characterization of such $m$'s is known.

In fact, if $\mathrm{ord}_m 3$ is relatively big, one would expect to find some power of $3$ in the desired interval. But the problem is that even if $\mathrm{ord}_m 3$ is very small, it could still happen that there's a solution just by coincidence.

As general as it's asked, I don't think this can be answered. The distribution of the residues of sequences of powers (in this case $3^a$) is a very hard problem with a lot of open questions.

Edit:

Gerry Myerson gave me an excellent example of what I was saying. Consider $m = 1093$. The sequence $(3^a-1) \bmod 1093$ takes only seven values $0, 2, 8, 26, 80, 242, 728$. Only one of them lands on the interval $(\frac{1093}{3},\frac{2\cdot 1093}{3}) = (364.333\ldots, 728.666\ldots)$ and just barely!!