The remainder can be negative?

Question

What is the remainder of the $13^{16} - 2^{25} 5^{15} \mod{3}$?

I resolved like this:

for $13^{16}\mod{3}\\$: \begin{align} 13 \equiv 1\mod{3} \to 13^{16} \equiv1 \mod{3}\\ \end{align}

for $2^{25}\mod{3}\\$: \begin{align} 2^2 \equiv 1 \mod{3}\\ 2^{20}\equiv 1 \mod{3}\\ 2^{20}*2^5 \equiv 2^5 \mod3\\ 2^{25} \equiv 2 \mod3 \end{align}

for $5^{15}\mod{3}\\$: \begin{align} 5\equiv 2 \mod{3}\\ 5^2\equiv4 \mod3\\ 5^2\equiv1 \mod3\\ 5^{14}*5\equiv 5 \mod3 \end{align}

So, $5^{15}\equiv5 \mod3 * 2^{25}\equiv2 \mod3 \to 2^{25}*5^{15}\equiv10 \mod3$ and \begin{align} 2^{25}*5^{15} \equiv10 \mod3\\ - 13^{16} \equiv 1 \mod3 \to\\ 13^{16}-2^{25}*5^{25} \equiv -9 \mod3 \end{align}

But for Euclidean algorithm the remainder is always positive. What's wrong?

Answer 1

Firstly, this isn't the Euclidean algorithm.

Secondly, if I understand correctly, you've worked out the remainder to be $1 - 10 \mod 3$. This is correct. The answer is $-9 \mod 3$, or, in a simpler form, $0 \mod 3$ (as $-9 \equiv 0 \mod 3$).