「中国人の剰余定理」を参考に、他5通りで計算してみた。

オリジナル
孫子算経の例＞

https://qiita.com/suharahiromichi/items/1a135d9648a0f55f020a#孫子算経の例

# 孫子算経より

https://ja.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E3%81%AE%E5%89%B0%E4%BD%99%E5%AE%9A%E7%90%86#:~:text=%E4%B8%AD%E5%9B%BD%E3%81%AE%E5%89%B0%E4%BD%99%E5%AE%9A%E7%90%86%EF%BC%88%E3%81%A1%E3%82%85%E3%81%86,%E8%AB%96%E3%81%AB%E3%81%8A%E3%81%91%E3%82%8B%E5%AE%9A%E7%90%86%E3%81%A7%E3%82%82%E3%81%82%E3%82%8B%E3%80%82


今物が有るが、その数はわからない。三つずつにして物を数えると[3]、二余る。五で割ると、三余る。七で割ると、二余る。物はいくつあるか？

答え：二十三。

解法：三で割ると、二余る数として、百四十と置く。五で割ると、三余る数として、六十三と置く。七で割ると、二余る数として、三十と置く。これらを足し合わせて、二百三十三を得る。これから二百十を引いて、答えを得る。一般に、三つずつにして物を数え、一余ると、その度に七十と置く[4]。五で割った余りに二十一をかける。七で割った余りに十五をかける。百六以上ならば、百五を引くことで、答えを得る。

以上wikipediaより


# 解法1: 手計算とwolframalphaのPowerModで
視聴時間14分22秒

https://youtu.be/e8DtzQkjOMQ

```
2,(  3), 35,  2,140
3,(  5), 21,  1, 63
2,(  7), 15,  1, 30
  (105)         233
                 23
```
分けて計算すると、面倒くさい事が分かりました。728? 758?
```
2,(  3),  5,  2, 20
3,(  5),  3,  2, 18
  ( 15)          38
                  8

8,( 15),  7, 13,728
2,(  7), 15,  1, 30
  (105)         758
                 23
```

~~逆元の計算がもっと簡単になりますか。~~（20220509）
手計算なのに？wolframalphaのPowerModで逆元の計算。

https://ja.wolframalpha.com/input?i=PowerMod%2835%2C-1%2C3%29%2CPowerMod%2821%2C-1%2C5%29%2CPowerMod%2815%2C-1%2C7%29&lang=en

https://ja.wolframalpha.com/input?i=PowerMod%283%2C-1%2C5%29%2CPowerMod%285%2C-1%2C3%29&lang=en

https://ja.wolframalpha.com/input?i=PowerMod%287%2C-1%2C15%29%2CPowerMod%2815%2C-1%2C7%29&lang=en


# 解法2: 解法1(手計算とwolframalphaのPowerModで)をvbaで

https://rosettacode.org/wiki/Category:VBA


```vb

Private Function mul_inv(a As Long, n As Long) As Variant
    If n < 0 Then n = -n
    If a < 0 Then a = n - ((-a) Mod n)
    Dim t As Long: t = 0
    Dim nt As Long: nt = 1
    Dim r As Long: r = n
    Dim nr As Long: nr = a
    Dim q As Long
    Do While nr <> 0
        q = r \ nr
        tmp = t
        t = nt
        nt = tmp - q * nt
        tmp = r
        r = nr
        nr = tmp - q * nr
    Loop
    If r > 1 Then
        mul_inv = "a is not invertible"
    Else
        If t < 0 Then t = t + n
        mul_inv = t
    End If
End Function
Sub aaa_mi()
    ActiveSheet.Cells.Clear
    Cells(1, 1) = 2
    Cells(2, 1) = 3
    Cells(3, 1) = 2
    Cells(1, 2) = 3
    Cells(2, 2) = 5
    Cells(3, 2) = 7
'
    m = Cells(1, 2) * Cells(2, 2) * Cells(3, 2)
    Cells(4, 2) = m
    Cells(1, 3) = m / Cells(1, 2)
    Cells(2, 3) = m / Cells(2, 2)
    Cells(3, 3) = m / Cells(3, 2)
    Cells(1, 4) = mul_inv(Cells(1, 3), Cells(1, 2))
    Cells(2, 4) = mul_inv(Cells(2, 3), Cells(2, 2))
    Cells(3, 4) = mul_inv(Cells(3, 3), Cells(3, 2))
    Cells(1, 5) = Cells(1, 1) * Cells(1, 3) * Cells(1, 4)
    Cells(2, 5) = Cells(2, 1) * Cells(2, 3) * Cells(2, 4)
    Cells(3, 5) = Cells(3, 1) * Cells(3, 3) * Cells(3, 4)
    Cells(4, 5) = Cells(1, 5) + Cells(2, 5) + Cells(3, 5)
    Cells(5, 5) = Cells(4, 5) Mod Cells(4, 2)
End Sub
' 2	3	35	2	140
' 3	5	21	1	 63
' 2	7	15	1	 30
' 	   105      233
' 			     23
```



# 解法3: wolframalphaのChineseRemainderで

https://www.wolframalpha.com/input?i=ChineseRemainder%5B%7B2%2C3%2C2%7D%2C+%7B3%2C5+%2C7+%7D%5D&lang=ja


結果
23

{}, {}の代わりに、[],[]でもできました。

ChineseRemainder[[2,3,2],[3,5,7]]

Result
23

# 解法4: SageMathCell で

https://sagecell.sagemath.org/

x = crt([2,3,2],[3,5,7]); x

23

# 解法5: sympyのsolve_congruenceを参考で

https://docs.sympy.org/latest/modules/ntheory.html#sympy.ntheory.modular.solve_congruence


# 解法6: ExcelVba で

nMax=100の根拠づけを教えて下さい。
nMax=105の方がいいように思えてきました。(20220505)

```vb
Const nMax = 100
Sub aaa_main()
    ActiveSheet.Cells.Clear
    iR = 0
    For i = 1 To nMax
        If i Mod 3 = 2 And i Mod 5 = 3 And i Mod 7 = 2 Then
           iR = iR + 1
           Cells(iR, 1) = i
        End If
    Next
End Sub
'23
```

# 感想

3～5世紀頃に、excelはありませんね。
歴史にifがあるとしたら、3～5世紀頃にexcelがあると、私は、今頃合同式をやってないと思います。


# 参考

https://www.ndl.go.jp/math/s1/c2.html

https://ja.wolframalpha.com/input?i=chinese+remainder+theorem&lang=en

https://doc.sagemath.org/html/en/reference/rings_standard/sage/arith/misc.html#sage.arith.misc.crt

共通テストも中国剰余定理関数でやってみたい。

https://qiita.com/mrrclb48z/items/03ac47c624f39c1d67a0

https://joho-ka.mints.ne.jp/chinese-remainder-theorem2?doing_wp_cron=1649156169.4035251140594482421875