Are there some known results for solving this kind of modular arithmetic problem?

Question

Preliminaries

Consider a number in the form:

$$x = a^n b - c,$$

where $a, b, c$ and $n$ are natural numbers. For which $n$ we can say that $x$ is divisible by $d$ with $a$ and $d$ coprime?

WLOG, consider the following example with $a=2$, $c=1$ and $d = 3$.

\begin{array}{llll} 2^{n}b - 1 \equiv 0 &(\text{mod}~ 3) & (1)\\ 2^{n}b - 1 + 3 \equiv 0 &(\text{mod}~ 3) & (\text{we add a multiple of $d=3$)}\\ 2^{n}b + 2 \equiv 0 &(\text{mod}~ 3) & (\text{we divide by a number (2) non divisible by $d=3$)}\\ 2^{n-1}b + 1 \equiv 0 &(\text{mod}~ 3) & (2) \\ 2^{n-1}b + 1 - 3\equiv 0 &(\text{mod}~ 3) & (\text{we subtract a multiple of $d=3$)}\\ 2^{n-1}b - 2\equiv 0 &(\text{mod}~ 3) & (\text{we divide by a number (2) non divisible by $d=3$)}\\ 2^{n-2}b - 1\equiv 0 &(\text{mod}~ 3) & (3). \end{array}

Reiterating this schema until I get $2^{n-n} = 2^0 = 1$, I conclude that

1. If $n$ is even (see equation (1) and (3)), then I need to prove

$$b - 1\equiv 0 ~(\text{mod}~ 3). $$

2. If $n$ is odd (see equation (2)), then I need to prove

$$b + 1\equiv 0 ~(\text{mod}~ 3). $$

Now, depending on $b$, I can find the answer to the initial question.

---

My question

I am wondering if the presented procedure has a name, or I can arrive to the conclusion by simply applying some known results that I'm missing.

Answer 1

Since $2+1=3$, it follows that $2+1\equiv0\pmod3$; i.e., $2\equiv-1\pmod3$.

Therefore $2^n\equiv(-1)^n\pmod3$.

$(-1)^n$ is $1$ when $n$ is even and $-1$ when $n$ is odd.

Therefore $2^n\equiv1\pmod3$ when $n$ is even and $2^n\equiv-1\pmod3$ when $n$ is odd.

So if $2^nb-1\equiv0\pmod3$ then $b-1\equiv0$ when $n$ is even and $-b-1\equiv0$ when $n$ is odd;

i.e., $b\equiv1$ when $n$ is even and $b\equiv-1\equiv2\pmod3$ when $n$ is odd.

Answer 2

Reformulated, denoting by $\mathbb{N}$ the set of nonnegative integers,

Given $a,b,c,d$ with $\gcd(a,d)=1$, what is $\{n\in\mathbb{N}\mid a^n b\equiv c\pmod{d}\}$?

We can reduce to the case $\gcd(b,d)=1$ (let $g=\gcd(b,d)$, $b=b'g$ and $d=d'g$; now if $d$ divides $a^n b-c$, then $g$ must divide $c$, and if we finally let $c=c'g$, then $d'$ divides $a^n b'-c'$, and now $\gcd(b',d')=1$).

In this case, $b$ has in inverse $b^{-1}$ modulo $d$, and we're looking for $N(a,b^{-1}c,d)$, where $$N(a,b,d)=\{n\in\mathbb{N}\mid a^n\equiv b\pmod{d}\}.$$ Let $m$ be the smallest element of this set. Then we have $$N(a,b,d)=\{m+kr\mid k\in\mathbb{N}\},$$ where $r$ is the smallest positive element of $N(a,1,d)$.

Thus the whole problem boils down to computing $r$ (which is called the order of $a$ modulo $d$) and $m$ (which is called the index, or discrete logarithm, of $b$ in base $a$ modulo $d$; note that it may not exist).

Both subproblems become very hard for large $d$. Known algorithms for the first one require complete factorization of $\varphi(d)$ (thus including that of $d$), the second one is even harder — see the link above.