大数取模 modulo arithmetic

春季美墨边境有3500位走线移民者，法院至少接受1位，至多接受全部的避难申请。请问总共有多少种接受方法？注意：该数字很大，只需要写出该数字除以\(10^9+7\)的余数。

解答：

每个走线者，要么被接受要么不被接受，有2种可能。所以有\(2^{3500}\)种可能。但不能所有人都不被接受，所以答案是\(2^{3500}-1\)。

但是题目难点在计算大数除以\(10^9+7\)的余数。

Modulo Arithmetic

In Euclidean division defined on integers \(\mathbb{Z}\), we write a=bq+r where q is quotient, r is remainder, \(b \neq 0\), \(0\leqslant r \leqslant |b|\).

If we only concern the remainder r, there are two forms of modulo operations we can use, the congruent modulo and the binary modulo. The congruent modulo form \(a\equiv r\pmod b\) reads “a and r are equivalent under modulo b”. The binary modulo form \(a \bmod b =r\) reads “the remainder of a divided by b is r”. Remember a and b can be negative.

Distributive laws

• (x + y) mod m = [(x mod m) + (y mod m)] mod m
• xy mod m = [(x mod m)(y mod m)] mod m

We can derive new properties from the distributive law of mutiplication.

$$
\begin{align*}
& x^2 \bmod n \\
=& xx \bmod n\\
=& [(x \bmod n)(x \bmod n)] \bmod n \\
=& (x \bmod n)^2 \bmod n \\
\end{align*}
$$

Similarly, we have \(b^e \bmod m = (b \bmod m)^e \bmod m\).

First use the distributive law of addition.

$$
\begin{align*}
& (2^{3500}-1) \bmod (10^9+7) \\
=& \left [2^{3500} \bmod (10^9+7) – 1 \bmod (10^9+7) \right ] \bmod (10^9+7) \\
=& \left [2^{3500} \bmod (10^9+7) – 1 \right ] \bmod (10^9+7)
\end{align*}
$$

Then we just zero in on \(2^{3500} \bmod (10^9+7)\).

Modular Exponentiation

Modular exponentiation is the form \(b^e \bmod m\) where m>0. \(2^{3500} \bmod (10^9+7)\) fits this form.

\(10^9+7\) has 10 digits in base 10, and we also know in computer science, int32 has 10 digits in base 10.

Let’s start trying \(2^{32}\) which equals 4294967296. \(2^{31}=2147483648\), still overshoot. \(2^{30}=1073741824\), it fits nicely with \(10^9+7\). \(2^{3500} \bmod (10^9+7) =2^{30\times 116+20} \bmod (10^9+7)\)

$$
\begin{align*}
& 2^{30\times 116+20} \bmod (10^9+7) \\
=& 2^{30\times 116}\times 2^{20} \bmod (10^9+7) \\
=& [2^{30\times 116} \bmod (10^9+7)] [2^{20} \bmod (10^9+7)] \bmod (10^9+7) \\
=& [1073741824^{116} \bmod (10^9+7)]\times 2^{20} \bmod (10^9+7) \\
=& [1073741824 \bmod 1000000007]^{116}\times 2^{20} \bmod (10^9+7) \\
=& (73741817^{116}\times 2^{20}) \bmod (10^9+7) \\
=& \left [73741817^{116} \bmod (10^9+7) \right ] \left [2^{20} \bmod (10^9+7) \right ] \bmod (10^9+7) \\
=& \left [73741817^{116} \bmod (10^9+7) \right ] \times 2^{20} \bmod (10^9+7) \\
\end{align*}
$$

Next, factorize 73741817. \(73741817^{116}=101^{116}\times 491^{116}\times 1487^{116}\). We need to find an exponentiation that is slightly greater than \(10^9+7 \).

\begin{align*}
101^p =& 10^9 \\
101^p =& 10^9 \\
\log_{10}101^p =& \log_{10} 10^9 \\
p\log_{10}101 =& 9 \\
p =& 4.49
\end{align*}

\(101^5=10510100501>1000000007\) and \(101^5 \bmod 1000000007 = 510100431\).

Similarly, \(\left \lceil \frac{9}{\log_{10} 491} \right \rceil = \left \lceil 3.34 \right \rceil = 4\). Hence, \(491^4=118370771 > 1000000007\), and \(491^4 \bmod 1000000007 = 120048155\).

\(\left \lceil \frac{9}{\log_{10} 1487} \right \rceil = \left \lceil 2.84 \right \rceil = 3\). Hence, \(1487^3=3288008303> 1000000007\), and \(1487^3 \bmod 1000000007 = 288008282\).

To save space, use m to present \(10^9+7 \).

$$
\begin{align*}
& \left [73741817^{116} \bmod (10^9+7) \right ] \times 2^{20} \bmod (10^9+7) \\
=& (101^{116}\times 491^{116} \times 1487^{116} \bmod m) \times 2^{20} \bmod m \\
=& (101^{116} \bmod m) \times (491^{116} \bmod m) \times (1487^{116} \bmod m) \times 2^{20} \bmod m \\
=& (101^{5\times 23+1} \bmod m) \times (491^{4\times 29} \bmod m) \times (1487^{3\times 38+2} \bmod m) \times 2^{20} \bmod m \\
=& (101^{5\times 23}\times 101 \bmod m) \times (491^{4\times 29} \bmod m) \times (1487^{3\times 38} \times 1487^2 \bmod m) \times 2^{20} \bmod m \\
=& \left [(101^{5\times 23}\bmod m) \times 101 \bmod m \right ] \times (491^{4\times 29} \bmod m) \times \left [(1487^{3\times 38}\bmod m) \times 1487^2 \bmod m \right ] \times 2^{20} \bmod m \\
=& \left [(101^5\bmod m)^{23} \times 101 \bmod m \right ] \times (491^4 \bmod m)^{29} \times \left [(1487^3\bmod m)^{38} \times 1487^2 \bmod m \right ] \times 2^{20} \bmod m \\
=& (510100431^{23} \times 101 \bmod m ) \times (120048155^{29}\bmod m) \times (288008282^{38}\bmod m) \times 2211169 \times 2^{20} \bmod m \\
=& (510100431^{23} \bmod m ) \times (120048155^{29} \bmod m) \times (288008282^{38}\bmod m) \times 223328069 \times 2^{20} \bmod m \\
\end{align*}
$$

We may fastforward \(223328069 \times 2^{20} \bmod (10^9+7)\) and get 451640512. Then factorize 510100431, 120048155, and 288008282.

• 510100431=3*617*275581
• 120048155=5*23*1043897
• 288008282=2*144004141

Round 2

\(p\leqslant 23\), \(\left \lceil \frac{9}{\log_{10} 3} \right \rceil = \left \lceil 18.86 \right \rceil = 19\). Hence, \(3^{19} \bmod 1000000007 = 162261460\).

\(p\leqslant 23\), \(\left \lceil \frac{9}{\log_{10} 617} \right \rceil = \left \lceil 3.22 \right \rceil = 4\). Hence, \(617^4 \bmod 1000000007 = 924113713\).

\(p\leqslant 23\), \(\left \lceil \frac{9}{\log_{10} 275581} \right \rceil = \left \lceil 1.65 \right \rceil = 2\). Hence, \(275581^2 \bmod 1000000007 = 944887036\).

\(p\leqslant 29\), \(\left \lceil \frac{9}{\log_{10} 5} \right \rceil = \left \lceil 12.88 \right \rceil = 13\). Hence, \(5^{13} \bmod 1000000007 = 220703118\).

\(p\leqslant 29\), \(\left \lceil \frac{9}{\log_{10} 23} \right \rceil = \left \lceil 6.61 \right \rceil = 7\). Hence, \(23^{7} \bmod 1000000007 = 404825426\).

\(p\leqslant 29\), \(\left \lceil \frac{9}{\log_{10} 1043897} \right \rceil = \left \lceil 1.49 \right \rceil = 2\). Hence, \(1043897^{2} \bmod 1000000007 = 720938986\).

\(p\leqslant 38\), \(\left \lceil \frac{9}{\log_{10} 2} \right \rceil = \left \lceil 29.89 \right \rceil = 30\). Hence, \(2^{30} \bmod 1000000007 = 73741817\).

\(p\leqslant 38\), \(\left \lceil \frac{9}{\log_{10} 144004141} \right \rceil = \left \lceil 1.10 \right \rceil = 2\). Hence, \(144004141^{2} \bmod 1000000007 = 479987537\).

$$
\begin{align*}
& (510100431^{23} \bmod m ) \times (120048155^{29} \bmod m) \times (288008282^{38}\bmod m) \times 223328069 \times 2^{20} \bmod m \\
=& \left [\left (3\times 617 \times 275581 \right )^{23} \bmod m \right ] \times \left [\left (5\times 23 \times 1043897 \right )^{29} \bmod m \right ] \times \left [\left (2\times 144004141 \right )^{38}\bmod m \right ] \times 451640512 \bmod m \\
=& \left [3^{23}\times 617^{23} \times 275581^{23} \bmod m \right ] \times \left[ 5^{29}\times 23^{29} \times 1043897^{29} \bmod m \right ] \times \left [ 2^{38}\times 144004141^{38}\bmod m \right ] \times 451640512 \bmod m \\
=& \left (3^{23} \bmod m \right ) \left (617^{23} \bmod m \right ) \left (275581^{23} \bmod m \right ) \\
& \left (5^{29} \bmod m \right ) \left (23^{29} \bmod m \right ) \left (1043897^{29} \bmod m \right ) \\
& \left (2^{38} \bmod m \right ) \left (144004141^{38} \bmod m \right )\times 451640512 \bmod m \\
=& \left (3^{19+4} \bmod m \right ) \left (617^{4\times 5 +3} \bmod m \right ) \left (275581^{2\times 11+1} \bmod m \right ) \\
& \left (5^{13\times 2+3} \bmod m \right ) \left (23^{7\times 4 +1} \bmod m \right ) \left (1043897^{2\times 14+1} \bmod m \right ) \\
& \left (2^{30+8} \bmod m \right ) \left (144004141^{2\times 19} \bmod m \right )\times 451640512 \bmod m \\
=& (3^{19}\times 3^{4} \bmod m ) (617^{4\times 5} \times 617^{3} \bmod m ) (275581^{2\times 11} \times 275581 \bmod m ) \\
& (5^{13\times 2} \times 5^3 \bmod m ) (23^{7\times 4} \times 23 \bmod m ) (1043897^{2\times 14}\times 1043897 \bmod m ) \\
& (2^{30}\times 2^{8} \bmod m ) (144004141^{2\times 19} \bmod m )\times 451640512 \bmod m \\
=& (3^{19} \bmod m \times 3^{4} \bmod m ) (617^{4\times 5} \bmod m \times 617^{3} \bmod m ) (275581^{2\times 11} \bmod m \times 275581 \bmod m ) \\
& (5^{13\times 2} \bmod m \times 5^3 \bmod m ) (23^{7\times 4} \bmod m \times 23 \bmod m ) (1043897^{2\times 14} \bmod m \times 1043897 \bmod m ) \\
& (2^{30} \bmod m \times 2^{8} \bmod m ) (144004141^{2\times 19} \bmod m)\times 451640512 \bmod m \\
=& (3^{19} \bmod m \times 3^{4} \bmod m ) ((617^4 \bmod m)^5 \times 617^{3} \bmod m ) ((275581^2 \bmod m)^{11} \times 275581 \bmod m ) \\
& ((5^{13} \bmod m)^2 \times 5^3 \bmod m ) ((23^7 \bmod m)^4 \times 23 \bmod m ) ((1043897^2 \bmod m)^{14} \times 1043897 \bmod m ) \\
& (2^{30} \bmod m \times 2^{8} \bmod m ) ((144004141^2 \bmod m)^{19})\times 451640512 \bmod m \\
=& (162261460 \times 3^{4} ) (924113713^5 \times 617^{3} ) (944887036^{11} \times 275581 ) \\
& (220703118^2 \times 5^3) (404825426^4 \times 23) (720938986^{14} \times 1043897 ) \\
& (73741817 \times 2^{8} ) (479987537^{19})\times 451640512 \bmod m \\
\end{align*}
$$

Round 3

• \(162261460=2^2\times 5\times251 \times32323\)
• 924113713=4127*223919
• \(944887036=2^2\times 236221759\)
• 220703118=2*3*36783853
• 404825426=2*97*1409*1481
• 720938986=2*360469493
• 73741817=101*491*1487
• 479987537=17*131*215531
• \(451640512=2^6\times23\times306821\)

Reorganize the expression

$$
\begin{align*}
=& (162261460 \times 3^{4} ) (924113713^5 \times 617^{3} ) (944887036^{11} \times 275581 ) \\
& (220703118^2 \times 5^3) (404825426^4 \times 23) (720938986^{14} \times 1043897 ) \\
& (73741817 \times 2^{8} ) (479987537^{19})\times 451640512 \bmod m \\
=& (2^2\times 5\times251 \times32323 \times 3^{4} ) ((4127\times223919)^5 \times 617^{3} ) ((2^2\times 236221759)^{11} \times 275581 ) \\
& ((2\times3\times36783853)^2 \times 5^3) ((2\times97\times1409\times1481)^4 \times 23) ((2\times360469493)^{14} \times 1043897 ) \\
& (101\times491\times1487 \times 2^{8} ) ((17\times131\times215531)^{19})\times 2^6\times23\times306821 \bmod m \\
=& (2^2 \times 5\times251 \times32323 \times 3^{4} ) ((4127\times223919)^5 \times 617^{3} ) (2^{22}\times 236221759^{11} \times 275581 ) \\
& (2^2\times 3^2\times36783853^2 \times 5^3) (2^4\times(97\times1409\times1481)^4 \times 23) (2^{14}\times(360469493)^{14} \times 1043897 ) \\
& (101\times491\times1487 \times 2^{8} ) ((17\times131\times215531)^{19})\times 2^6\times23\times306821 \bmod m \\
=& (2^{2+22+2 +4+14+8+6} \times 5^{1+3} \times251 \times32323 \times 3^{4+2} ) ((4127\times223919)^5 \times 617^{3} ) ( 236221759^{11} \times 275581 ) \\
& (36783853^2 ) ((97\times1409\times1481)^4 \times 23^2) (360469493^{14} \times 1043897 ) \\
& (101\times491\times1487 ) ((17\times131\times215531)^{19})\times306821 \bmod m \\
=& (2^{58} \times 5^4 \times251 \times32323 \times 3^6 ) ((4127\times223919)^5 \times 617^{3} ) ( 236221759^{11} \times 275581 ) \\
& (36783853^2 ) ((97\times1409\times1481)^4 \times 23^2) (360469493^{14} \times 1043897 ) \\
& (101\times491\times1487 ) ((17\times131\times215531)^{19})\times306821 \bmod m \\
\end{align*}
$$

Up to now, we have to use a computer. See Code for 大数取模 modulo arithmetic.