When using the extended Euclidean algorithm, can you add the integer to make the answer positive?

Question

I'm currently solving some tasks where I need to use the Chinese Remainder Theorem. To calculate $y_i$, I use the extended Euclidean algorithm. An example of how I find $y_1$ in a task with $y_1,y_2,y_3$:

$x_0 = a_1M_1y_1+a_2M_2y_2+a_3M_3y_3$

$110=12·9+2$

$9=4·2+1$

$1=9-4·2$

$1=9-4(110-12·9)$

$1=49·9-4·110$

The coefficient to 110, is -4. I thought that this would be the correct answer for $y_1$, but when using a online calculator, I got the answer $5$. But this is because $5 = -4+9$. Is it possible to use the negative integer as a solution, or will I have to use the postive one?

Thanks for the help.

Answer 1

You have that $110\equiv 2 \bmod 9$. The inverse of $2 \bmod 9$ is $5$ (since $5\times 2 \equiv 10 \equiv 1 \bmod 9$), and $5 \equiv -4 \bmod 9$, so $-4$ is also the multiplicative inverse of $2\bmod 9$ (since $-4\times 2 \equiv -8 \equiv 1 \bmod 9)$.

You can certainly use the negative integer version as part of the subsequent solution, and indeed it is often advantageous to flip to using negative equivalence values.