Finding smallest nonnegative integer x in a modulo equation

Question

-36789 = x mod 19

So what I have done is the following

1. 36789/19 = 1936.263158.... = 1937 (round up)

2. (1937 * 19) - 36789 = 14 <- assumed final answer

But I am unsure if the final answer is correct, as I am new to this modulo arithmetic.

I have read online modulo arithmetic, but unable to find a scenario like the above question.

The typical example is -36789 mod 19 = 14 (which the assumed final answer)...

Answer 1

You did it right.

$r$ is the smallest positive modulo iff: $0 \leq r < m$ (where $m$ is modulus.)

In your problem $r=14,m=18$:

$0 \leq 14 < 19$

Or in other words: $-36789=19k+14$

The general formula would be:

$([n/m]+1)\cdot m-n=r$

Answer 2

You are looking for the smallest non-negative value for $-36789+19n$, because that is equivalent to the $-36789$ $mod$ $19$. Therefore, it is clear that when $n<1937$, $-36789+19n <0$, when $n>1937$, $-36789+19n >0$ and $-36789+19n$ is strictly increasing. Hence, $1937$ is the value for n that will create the smallest non-negative value for $-36789+19n$. Consequently, $-36789+19*1937=14$.