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.


You can do this two steps :

  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$.

This is (probably) the best one can do without knowing anything about the numbers in question.

  • $\begingroup$ I'm a bit confused about that last part. Are you saying one of the ns that work is mr? In that case, if we take t = 6, r = 7 and q = 10, d would be 1, m would be 6 and n would be 42. 42 * 7 is 294 which is not congruent with 6 mod 10. $\endgroup$ – Luka Horvat Oct 15 '13 at 16:51
  • $\begingroup$ @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}$ $\endgroup$ – Prahlad Vaidyanathan Oct 15 '13 at 16:54
  • $\begingroup$ Nice solution. To get the smallest n, all that's left to do is get the remainder of the n / (q / d) division (if I'm not mistaken). Since the right side repeats every q / d ns. $\endgroup$ – Luka Horvat Oct 15 '13 at 17:00
  • $\begingroup$ 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. $\endgroup$ – Luka Horvat Oct 15 '13 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.