Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.