First index of number in that arithmetic progression which is a multiple of the given prime number

I have a prime number $p$, an arithmetic progression starting at $a$ with common difference $d$. How to find the first index of a term in that arithmetic progression which is a multiple of the given prime number $p$?

Example: $$ a = 4,\quad d = 9,\quad p = 11. $$

The sequence is $4,13,22,31,\dotsc$; the first index such that the term is divisible by $p$ is $2$, because $22\bmod 2 = 0$.

If no such term exists, give answer as $-1$.

Brute force works but takes a lot of time. Is there any alternative approach?

The $k$-th term of the progression is $a+kd$, so you need to solve $$ a+kd\equiv0\pmod{p} $$ or $$ kd\equiv -a\pmod{p} $$ which has surely a solution whenever $d$ is not a multiple of $p$; in this case take $e$ an inverse of $d$ modulo $p$, so the equation becomes $$ k\equiv -ae \pmod{p} $$

In your example the inverse of $9$ modulo $11$ is $5$, as $9\cdot 5=45\equiv 1\pmod{11}$. So the solution is $$ k\equiv (-4)\cdot 5\equiv -20\equiv 2\pmod{11} $$ In general you find the inverse modulo $p$ with the extended Euclidean algorithm.

If $d\equiv0\pmod{p}$ there is no solution.

I assume the interesting case $\gcd(d,p)=1,\;$ i.e. $d$ has in inverse mod p. You want to solve $a + xd = Ip$. Compute $x=-ad^{-1} \pmod p$ and then the index $I$ is $\frac{a+xd}{p}$. In your case $$9^{-1} \equiv 5 \pmod {11}$$ $$x=-ad^{-1}=(-4\times5) \equiv 2 \pmod {11}$$ $$I = \frac{4+2\times 9}{11}=\frac{22}{11} = 2$$