# Find $n$ that satisfies $t\equiv nr\pmod{q}$, if such $n$ exists.

So basicially, given the equation $t\equiv nr\pmod{q}$ where $t,r\in\mathbb{N_0}$ and $n, q\in\mathbb{N}$ find $n$ if the rest of the variables are defined.

I've figured out a way to see if there is a solution. It appears that if the largest common divisor of $r$ and $q$ divides $t$, the solution exists. I'm not sure if this covers all the cases and I don't know how to prove it's true.

The question is, how do I find out how many times I need to add $r$ to get $t\pmod{q}$?

Edit: Obviously, if one such $n$ exists, then there are infinite $n$s for which it works. I need the smallest one.

1. Use the Extended Euclidean Algorithm to find the GCD $d = (r,q)$ and the Bezout coefficients $x$ and $y$ such that $$d = rx + qy$$
2. Now $t = nr\pmod q$ iff $d\mid t$. So find $m = t/d$, then $$t = md = mrx + mqy$$ so take $n = mx$.
• @Darwin : I meant $n = mx$, not $mr$. Apologies :) [In the situation you described, $1 = 3\cdot 7 - 2\cdot 10$, so $n = 6\cdot 3 = 18$, and $6 \equiv 18\cdot 7\pmod{10}$ – Prahlad Vaidyanathan Oct 15 '13 at 16:54
• Actually, if I'm right, finding x and y dissolves into this exact problem, doesn't it? $x = \frac{qy - d}{r}$ where we need to find $y$ that makes $x$ a whole number. This means that $qy \equiv d\pmod{r}$, and around we go. – Luka Horvat Oct 15 '13 at 17:07