# How would you compute this modulo problem?

$$(10^{18}-1)(10^{18}-1) \bmod 10^{18}$$ I am solving a programming problem and I hold my integers in 64 bit long long integers. Above is a particular case I am unable to solve. $(ab)\bmod m = (a \bmod m)(b \bmod m)\bmod m$, doesn't hold here as $(a \bmod m)(b \bmod m)$ would still overflow a 64 bit integer. How do I solve this? I took 18th power only as an example. The problem holds even for all the integers in the range $(10^{11}, 10^{18}-1)$.

-
$10^{18}=0\mod 10^{18}$. – Pedro Tamaroff Jan 3 '14 at 21:28
I guess the example is just that, an example, and you're looking for a way to do the multiplication for any two large remainders without overflow? That's more a programming question than a mathematics question. Check stackoverflow.com/questions/16426557/… for an algorithm. – Daniel Fischer Jan 3 '14 at 21:38

Remember that $a \equiv b \pmod{n}$ if and only if $n\mid(a-b)$.
It follows that $a \bmod a = 0$, and $a-1 \equiv (-1) \pmod{a}$, because $a\mid((a-1)-(-1))$, i.e. $a\mid a$.
We have $10^{18}-1 \pmod{10^{18}}$, so it is equivalent to $(-1) \pmod{10^{18}}$. So the expression $(10^{18}-1) \cdot (10^{18}-1) \pmod{10^{18}}$ is equivalent to $(-1) \cdot (-1) \pmod{10^{18}}$ which is equivalent to $1$.