<s>[INST] Algebra/number theory solution check, number of 0's at end of integer As part of a larger problem, I wish to calculate the value of $\frac{1993^2+1993}{2} \pmod {2000}$. The top reduces to $42$. However, $\gcd(2,2000)>1$, so the solution is not $21$, and carrying out the division would require changing the modulus. 
Is there a method to divide in this case (or in a general case entirely applicable to this case), such that doing this division will not change the modulus from 2000, i.e. the solution $x$ is $\frac{1993^2+1993}{2} \equiv x \pmod {2000}$. 
I understand that I can just do the arithmetic, but I wonder if it is possible to keep the modulus at $2000$ after the division.
 [/INST] $1993^2 + 1993 \equiv (-7)^2 +(-7) \equiv 42\pmod {2000}$.
So $\frac {1993^2+1993}2 \equiv \frac {42}2 \pmod {\frac {2000}{\gcd(2,2000)}}$
So $x \equiv 21\pmod{1000}$ so $x \equiv 21, 1021 \pmod {2000}$
$2000 = 125*16$ and if we consider the chinese remainder theorem we get that $x \equiv 21 \pmod{125}$ 
But to solve $x \pmod{16}$ we solve $1993^2 + 1993\pmod{32}\equiv 9^2 +9\equiv 26\pmod {32}$.
So $\frac{1993^2 + 1993}2 \equiv \frac{32k +26}2\equiv 16k + 13 \equiv 13 \equiv -3\pmod {16}$.
And as $21 \not \equiv -3\pmod{16}$ then $x\equiv 21 \pmod {2000}$ can't be the solution.
So it must be $x \equiv 1021 \pmod{2000}$.
</s>