# Some fast way to find a solution set to $us+vt \equiv 0 \pmod d$

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.

-
The answer to the first part is the Euclidean algorithm; see in particular the subsections on Bézout's identity and the extended Euclidean algorithm. –  Harald Hanche-Olsen Nov 3 '12 at 11:57
any more comment? –  La Ventana Nov 3 '12 at 15:56
When someone points you to a Wikipedia article that contains a full explanation, it's usually not a good idea to just ask for an explanation again; few people enjoy rewriting articles again from scratch that already exist. If you don't understand the explanation in the article, a more promising approach would be to point out specifically which part of the explanation you're having trouble understanding; then someone could specifically explain that part. –  joriki Nov 5 '12 at 8:49