百五減算のメモ

3で割ると2余り，5で割ると1余り，7で割ると2余る最小の正整数はいくつか？

のような問題で，和算では百五減算と言われている問題があります．

答えは
$70\cdot 2 + 21 \cdot 1 + 15 \cdot 2 = 191$
と計算した191から105を引くと86が出ます．

ここで86が正解です．

この問題は非常に暇で仕方なかったので友人にぶん投げた問題です．
shibiremath.hatenablog.com
結構素直にやってもらっているので，直感的で分かりやすいと思います．

解答の解説

これは

3で割ると $A_1$ 余り，5で割ると $A_2$ 余り，7で割ると $A_3$ 余る最小の正整数はいくつか？

といった問題に置き換えることができて
$70A_1 + 21A_2 + 15A_3$
を計算し，105を引けるだけ引いた結果が答えになります．

2変数の場合

最初は $n_1 \perp n_2$ となる整数 $(n_1,n_2)$ を用いた連立方程式
$a \equiv a_1 \pmod{n_1}$
$a \equiv a_2 \pmod{n_2}$
の解 $a$ について考えてみます．
これは
$a_2 n_1 x + a_1 n_2 y$
が $a$ の解の1つになります．

確認としては $n_1 \perp n_2$ という条件から
$n_1 x + n_2 y = 1$
に解 $(x,y)$ が存在し
$n_2 y = 1 - n_1 x$
と書けますね．
これは
$a_2 n_1 x + a_1 n_2 y = a_2 n_1 x + a_1(1 - n_1 x) = n_1 x(a_2 - a_1) + a_1$
になるので
$a \equiv a_1 \pmod{n_1}$
を満たします．
同様にして
$a \equiv a_2 \pmod{n_2}$
を満たすこともわかります．

また，この解は $n_1n_2$ を法として合同です．
解 $b$ が存在したとして
$a-b \equiv 0 \pmod{n_1}$
$a-b \equiv 0 \pmod{n_2}$
が成立し， $a-b$ は $n_1n_2$ の公倍数になるからですね．

2変数の場合まとめ

2式の連立方程式
$a \equiv a_1 \pmod{n_1}$
$a \equiv a_2 \pmod{n_2}$
の解は， $n_1x + n_2y = 1$ となる $(x,y)$ を用いて
$a = a_2 n_1 x + a_1 n_2 y$
で得られ，解は $a$ に対して $n_1n_2$ を法として合同になる．

例えば

5で割ると1余り，7で割ると4余る最小の正整数はいくらか？

という問題には
$5x + 7y = 1$ の解 $(x,y) = (3,-2)$ を用いて
$5\cdot 3\cdot 4 + 7\cdot (-2) \cdot 1 = 46$
になるので，35を引いた11が答えになります．

多変数の場合

次にどの2数をとっても互いに素になる整数 $(n_1,n_2,\cdots,n_k)$ を用いた連立方程式
$a \equiv a_1 \pmod{n_1}$
$a \equiv a_2 \pmod{n_2}$
$\cdots$
$a \equiv a_k \pmod{n_k}$
について考えます．

ここで $b_t$ を $\{n\}$ を $n_t$ 以外全て乗じた数とします．
簡単に記すなら $N = \prod_{s=1}^{k} n_s$ として $b_t = \frac{N}{n_t}$ になります．
今回の連立方程式の解 $a$ は
$a = \sum_{s=1}^{k}b_s x_s a_s$
になります．

確認としては $t$ に対して $\pmod {n_t}$ について考えると， $b_t$ は互いに素なので
$\sum_{s=1}^{k}b_s x_s a_s \equiv b_t x_t a_t \pmod{n_t}$
になります．
$b_t$ と $n_t$ は互いに素になるので
$b_t x_t + n_t y_t = 1$
の解 $(x_t, y_t)$ が存在し，
$b_t x_t a_t = a_t(1 - n_t y_t) \equiv a_t \pmod{n_t}$
になることからわかりますね．

また解は2変数の場合と同様にして， $a$ に対して $n_1n_2\cdots n_k$ を法として合同になることがわかります．

多変数の場合まとめ

連立方程式
$a \equiv a_1 \pmod{n_1}$
$a \equiv a_2 \pmod{n_2}$
$\cdots$
$a \equiv a_k \pmod{n_k}$
の解 $a$ は， $N = \prod_{s=1}^{k} n_s$ として $b_t = \frac{N}{n_t}$ と，各 $b_tx_t + n_ty_t = 1$ の解 $(x_t, y_t)$ を用いて
$a = \sum_{s=1}^{k}b_s x_s a_s$
になる．
他の解は $a$ に対して $n_1n_2\cdots n_k$ を法として合同になる．

最初の

3で割ると2余り，5で割ると1余り，7で割ると2余る最小の正整数はいくつか？

の答えについては，
$5\cdot 7 x_1 + 3y_1 = 35x_1 + 3y_1 = 1$
の解は $(x_1,y_1) = (2,-23)$ ，
$3\cdot 7 x_2 + 5y_2 = 21x_2 + 5y_2 = 1$
の解は $(x_2,y_2) = (1,-4)$ ，
$3\cdot 5 x_3 + 7y_3 = 15x_3 + 7y_3 = 1$
の解は $(x_3,y_3)=(1,-2)$
になりますので
$\frac{3\cdot 5\cdot 7}{3}\cdot x_1 \cdot a_1 + \frac{3\cdot 5\cdot 7}{5}\cdot x_2 \cdot a_2 + \frac{3\cdot 5\cdot 7}{7}\cdot x_3 \cdot a_3$
を計算して
$70 a_1 + 21 a_2 + 15 a_3$
に代入したら答えになります．