Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$$ (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)$.

share|improve this question
2  
$10^{18}=0\mod 10^{18}$. –  Pedro Tamaroff Jan 3 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 at 21:38

1 Answer 1

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.