Random Answer, Correct!

How would we find that $21 \cdot 7^{10} \cdot 6^{20} \equiv 504 \pmod{1000}$ and $13^{30} \equiv 49 \pmod{1000}$ without a calculator?

In this question, I used the calculator to make my work less tedious. You can choose to work without a calculator, but it would take a lot of time. We use the multiplicative property of modular arithmetic such that if $a_{1}\equiv b_{1} \mod n$ and $a_{2}\equiv b_{2} \mod n$ , then $a_{1}a_{2}\equiv b_{1}b_{2} \mod n$ .

We shall start with $p=C_{1}^{21}\times7^{10}\times6^{20}$ . First we prime factorize $p$ into $7^{11}\times3^{21}\times2^{20}$ . So, $7^{11}\times3^{21}\times2^{20}\equiv k \mod 1000$ .

$7^{3}\equiv 343 \mod 1000$ , $3^{7}\equiv 187 \mod 1000$ , $2^{10}\equiv 24 \mod 1000$

$7^4\equiv 401 \mod 1000$ , $(3^{7})^{3}\equiv 187^{3} \mod 1000$ , $(2^{10})^{2}\equiv 576 \mod 1000$

$(7^{4})^{2}\times7^{3}\equiv (401)^{2}(401) \mod 1000$

So, the last 3 digits of $(343)(401)^{2}$ is $743$ , $187^{3}$ is $203$ and $576$ . Therefore, the last $3$ digits of $p$ is $k=743\times203\times576\equiv \boxed{504} \mod 1000$ .

Now, we have to find last $3$ digits of $13^{30}$ . $13^{5}\equiv 293 \mod 1000$ $(13^{5})^{2}\equiv 849 \mod 1000$ $((13^{5})^{2})^{3}\equiv \boxed{49} \mod 1000$

Finally, using the additive property of modular arithmetic, we can finally find the last $3$ digits of $p+q\equiv 504+49 \mod 1000$ . Therefore the last $3$ digits is $504+49=\boxed{553}$ .

How you got 504 and 49. I could not get these values even using MS excel :)

i didn't get dis... pls help me to understand "the concept of mod".

Notice that the given problem models the binomial probability distribution $\textrm{Bin}(30,7/13)$ .