0

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.

Luka Horvat
  • 2,618

1 Answers1

1

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.

Prahlad Vaidyanathan
  • 31,554
  • 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. – Luka Horvat Oct 15 '13 at 16:51
  • @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
  • 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. – Luka Horvat Oct 15 '13 at 17:00
  • 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