大数取模 modulo arithmetic

2024年5月18日

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

解答:

每个走线者,要么被接受要么不被接受,有2种可能。所以有23500种可能。但不能所有人都不被接受,所以答案是235001

但是题目难点在计算大数除以109+7的余数。

Modulo Arithmetic

In Euclidean division defined on integers Z, we write a=bq+r where q is quotient, r is remainder, b0, 0r|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 ar(modb) reads “a and r are equivalent under modulo b”. The binary modulo form amodb=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.

x2modn=xxmodn=[(xmodn)(xmodn)]modn=(xmodn)2modn

Similarly, we have bemodm=(bmodm)emodm.

First use the distributive law of addition.

(235001)mod(109+7)=[23500mod(109+7)1mod(109+7)]mod(109+7)=[23500mod(109+7)1]mod(109+7)

Then we just zero in on 23500mod(109+7).

Modular Exponentiation

Modular exponentiation is the form bemodm where m>0. 23500mod(109+7) fits this form.

109+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 232 which equals 4294967296. 231=2147483648, still overshoot. 230=1073741824, it fits nicely with 109+7. 23500mod(109+7)=230×116+20mod(109+7)

230×116+20mod(109+7)=230×116×220mod(109+7)=[230×116mod(109+7)][220mod(109+7)]mod(109+7)=[1073741824116mod(109+7)]×220mod(109+7)=[1073741824mod1000000007]116×220mod(109+7)=(73741817116×220)mod(109+7)=[73741817116mod(109+7)][220mod(109+7)]mod(109+7)=[73741817116mod(109+7)]×220mod(109+7)

Next, factorize 73741817. 73741817116=101116×491116×1487116. We need to find an exponentiation that is slightly greater than 109+7.

101p=109101p=109log10101p=log10109plog10101=9p=4.49

1015=10510100501>1000000007 and 1015mod1000000007=510100431.

Similarly, 9log10491=3.34=4. Hence, 4914=118370771>1000000007, and 4914mod1000000007=120048155.

9log101487=2.84=3. Hence, 14873=3288008303>1000000007, and 14873mod1000000007=288008282.

To save space, use m to present 109+7.

[73741817116mod(109+7)]×220mod(109+7)=(101116×491116×1487116modm)×220modm=(101116modm)×(491116modm)×(1487116modm)×220modm=(1015×23+1modm)×(4914×29modm)×(14873×38+2modm)×220modm=(1015×23×101modm)×(4914×29modm)×(14873×38×14872modm)×220modm=[(1015×23modm)×101modm]×(4914×29modm)×[(14873×38modm)×14872modm]×220modm=[(1015modm)23×101modm]×(4914modm)29×[(14873modm)38×14872modm]×220modm=(51010043123×101modm)×(12004815529modm)×(28800828238modm)×2211169×220modm=(51010043123modm)×(12004815529modm)×(28800828238modm)×223328069×220modm

We may fastforward 223328069×220mod(109+7) and get 451640512. Then factorize 510100431, 120048155, and 288008282.

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

Round 2

p23, 9log103=18.86=19. Hence, 319mod1000000007=162261460.

p23, 9log10617=3.22=4. Hence, 6174mod1000000007=924113713.

p23, 9log10275581=1.65=2. Hence, 2755812mod1000000007=944887036.

p29, 9log105=12.88=13. Hence, 513mod1000000007=220703118.

p29, 9log1023=6.61=7. Hence, 237mod1000000007=404825426.

p29, 9log101043897=1.49=2. Hence, 10438972mod1000000007=720938986.

p38, 9log102=29.89=30. Hence, 230mod1000000007=73741817.

p38, 9log10144004141=1.10=2. Hence, 1440041412mod1000000007=479987537.

(51010043123modm)×(12004815529modm)×(28800828238modm)×223328069×220modm=[(3×617×275581)23modm]×[(5×23×1043897)29modm]×[(2×144004141)38modm]×451640512modm=[323×61723×27558123modm]×[529×2329×104389729modm]×[238×14400414138modm]×451640512modm=(323modm)(61723modm)(27558123modm)(529modm)(2329modm)(104389729modm)(238modm)(14400414138modm)×451640512modm=(319+4modm)(6174×5+3modm)(2755812×11+1modm)(513×2+3modm)(237×4+1modm)(10438972×14+1modm)(230+8modm)(1440041412×19modm)×451640512modm=(319×34modm)(6174×5×6173modm)(2755812×11×275581modm)(513×2×53modm)(237×4×23modm)(10438972×14×1043897modm)(230×28modm)(1440041412×19modm)×451640512modm=(319modm×34modm)(6174×5modm×6173modm)(2755812×11modm×275581modm)(513×2modm×53modm)(237×4modm×23modm)(10438972×14modm×1043897modm)(230modm×28modm)(1440041412×19modm)×451640512modm=(319modm×34modm)((6174modm)5×6173modm)((2755812modm)11×275581modm)((513modm)2×53modm)((237modm)4×23modm)((10438972modm)14×1043897modm)(230modm×28modm)((1440041412modm)19)×451640512modm=(162261460×34)(9241137135×6173)(94488703611×275581)(2207031182×53)(4048254264×23)(72093898614×1043897)(73741817×28)(47998753719)×451640512modm

Round 3

  • 162261460=22×5×251×32323
  • 924113713=4127*223919
  • 944887036=22×236221759
  • 220703118=2*3*36783853
  • 404825426=2*97*1409*1481
  • 720938986=2*360469493
  • 73741817=101*491*1487
  • 479987537=17*131*215531
  • 451640512=26×23×306821

Reorganize the expression

=(162261460×34)(9241137135×6173)(94488703611×275581)(2207031182×53)(4048254264×23)(72093898614×1043897)(73741817×28)(47998753719)×451640512modm=(22×5×251×32323×34)((4127×223919)5×6173)((22×236221759)11×275581)((2×3×36783853)2×53)((2×97×1409×1481)4×23)((2×360469493)14×1043897)(101×491×1487×28)((17×131×215531)19)×26×23×306821modm=(22×5×251×32323×34)((4127×223919)5×6173)(222×23622175911×275581)(22×32×367838532×53)(24×(97×1409×1481)4×23)(214×(360469493)14×1043897)(101×491×1487×28)((17×131×215531)19)×26×23×306821modm=(22+22+2+4+14+8+6×51+3×251×32323×34+2)((4127×223919)5×6173)(23622175911×275581)(367838532)((97×1409×1481)4×232)(36046949314×1043897)(101×491×1487)((17×131×215531)19)×306821modm=(258×54×251×32323×36)((4127×223919)5×6173)(23622175911×275581)(367838532)((97×1409×1481)4×232)(36046949314×1043897)(101×491×1487)((17×131×215531)19)×306821modm

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