Apologies if I am not using the correct terms - I have never really studied modular arithmetic properly (Physics background). However, I am now playing with a cryptography problem and I have managed to reduce it down to the following:
Suppose you have a linear expression with two variables $x$ and $y$ in mod $p$, where $p$ is a large prime number: $$ a\,x + b\,y + c = 0 \mod p$$ You know that this expression has roots $x_0 < p, y_0 < p$, i.e. I am not interested in the infinite set of roots $x = x_0 + np$ and $y = y_0 + np$ but only in the integer roots in the range $(0, p)$. You don't know the values of the roots, you just know they exist.
Can you construct a new expression in mod $q$ of the form: $$ A(a, b, c, p)\,x + B(a, b, c, p)\,y + C(a, b, c, p) = 0 \mod q $$ such that it has the same roots $x_0, y_0$. You are free to choose any $q > p$ (for my particular needs, the bigger $q$, the better) and any functions $A, B, C$ (excluding of course the trivial $A = B = C = 0 \mod q$ case).