1) Suppose that $u,v,d$ are nonzero, unequal fixed/given natural number. $s,t$ are nonzero natural numbers. We want to find a solution set $(s,t)$ that satisfies $us+vt \equiv 0 \pmod d$. What would be a fast way to discover one solution?
2) Following from 1), we want to find (s,t) that $us-vt$ does not contain some particular prime number $p$ in its($us-vt$) prime factorization form. What would be a general way to find such set? (For example, $p$ being $3$)
Edit: about 1): if this can be solved by the Euclidean algorithm, can anyone show how it works? I am not really getting why the Eculidean algorithm works at here.