[preface, i'll use '%' as the modulo or remainder operator, as it is in C and many other programming languages, where for example 10 % 7 == 3]
i'm looking for an algorithm to solve for n in
(A*n + B) % C == 0
where A, B, and C are all positive integers.
i have additional constraints on my particular problem that i don't think are important for the solution. (namely, A is less than C, A is a power of 3, C is a power of 2, and B is odd, all of which i believe imply that n must be odd.) (and yes, i'm toying with Collatz here)
i can brute force this (try all possible n from 0 to C-1), but that will become time consuming as C increases. i could also try to binary search for it, which would be a performance improvement, but i'm looking for a more efficient algorithm.
Translating to more standard number theory, you want a solution to $$ An\equiv-B\pmod C $$ The first step to a solution is to solve $$ Am\equiv 1\pmod C $$ We then get $n=-Bm$ by multiplying both sides with $-B$.
The extended Euclidean algorithm gives you two integers $m, m'$ such that $$ Am+Cm'=1 $$ (as your additional constraints tell us that $\gcd(A,C)=1$). This finishes the solution. A solution between $0$ and $C$ is not guaranteed in this case, so taking $n\%C$ at the end will give you that.