2
$\begingroup$

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.

  • 0
    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.2012-11-05

0 Answers 0