After going through easily a couple dozen answers here (in particular by @BillDubuque) and articles elsewhere, I'm still stumped something that seems like it ought to be simple. First, here's the setup; all variables are non-zero integers.
Lemma: Given $(a,b) = 1$ and $(a, c,d)=1$, and $a > b \geq 1$:
$$ \left\{ \begin{array}{lr} u = ax + bc \\ v = ay + bd \\ \end{array} \right\} \iff \left(u \mid v \iff y \equiv c'dx \pmod u \right) $$
where $c'$ is the modular inverse of $c$ in modulus $u$, because I hate typing the exponent every time.
Proof (Sketch): The required coprimes ensure all our variables have unique modular inverses. Thus, starting with $u = ax + bc \equiv 0 \pmod u$, and continuing in the same modulus:
$$ax \equiv -bc \iff adx \equiv -bcd \\ u \mid v \iff u \equiv v \equiv 0 \iff ay \equiv -bd \iff acy \equiv -bcd \\ acy \equiv adx \iff cy \equiv dx \iff y \equiv c'dx$$
This was discussed some in a simpler form in this post and its answers.
This has been useful in analyzing sequences like this, in particular examining which primes divide the numbers generated by each entry. But I've run up against a bit of a wall with modular inverses in a variable modulus.
Let $a=15, b=1, c=-7, d=2$. In addition, $x>0$ is even and $u$ is prime. (This formulation asks: What primes of the form $15k-7$ (with $k$ even), e.g. $[23, 53, 83, \dots]$ divide numbers of the form $15n +2$ (with $n$ odd), e.g. $[17, 47, 77, \dots]$?)
To find $y = c'dx$, we need to solve for $c'$, giving the equation
$$-7c' \equiv 1 \pmod{15x-7}$$
and $c'$ should be a function of $x$. And I can't find a way to do it. I know the solution but I don't know how to show the process of getting to that solution. Extended Euclidean algorithm, polynomial long division, throwing things into Sage to see what comes out... either I get no solution, conflicting values, or infinite loops.
The solution (or one form of it), determined empirically (it's not hard to force a computer to calculate a few hundred thousand inverses), is $c' \equiv 2-x' \pmod {15x-7}$.
But I can't prove it, or show where it came from. Is the problem that there are some values of $x$ (i.e., $x = 7k$) for which there is no answer, therefore no general solution exists that one can readily solve? Does anyone have thoughts on how to solve what I feel like should be a simple modular inverse?
Edit to add: an example of a congruence similar to this that is solvable is $2a \equiv 1 \pmod {2x+1}$, for which the solution is $a \equiv x+1$. $2$ has a modular inverse in any odd modulus. Similarly, $x$ is its own inverse mod $x+1$. Is there a method of determining when these problems have solutions, and when they don't? Is it merely a matter of "if it's possible for the integer or polynomial you're trying to invert to not be coprime to the modulus, it can't be solved"?
