AP term multiple of prime number

Question

I am having this equation :

(a+(n-1)d)%p=0

Here a and d can go upto 10^18 and p is prime number upto 10^9 .

How to find the least value of n here?

Example : If a=4 and d=9 with p=11 then here answer is 3.

As (4+18)%11 = 0

Answer 1

You have $$ a+(n-1)d\equiv0\pmod p $$ and want to solve for n. You can solve it formally, as though it was an equation, to get $$ n\equiv1-a/d\pmod p $$

Now you can use the extended Euclidean algorithm to find $a/d\pmod p$ and substitute.