ライバルのテストの点数を連立一次合同式で暴いてみた

数学のテスト。

ライバルの点が知りたい！

でも恥ずかしくて聞けない。

そんなことはありませんか？

連立一次合同式の解法

学生時代、ライバルとテストの点を競い合った経験がある人も多いことでしょう。

しかし、面と向かって相手にテストの点を聞くのは、

少々野暮というか、謎のプライドが邪魔をして上手く聞き出せないものです（マスタノ調べ）

しかし、直接点数を聞くのではなく、余りくらいなら気兼ねなく聞けます。

テストの点を３，５，７で割った余りがそれぞれいくつか聞いてみましょう。

～寸劇～

じゅん「中間テスト、数学はどうだった？」

ライバル「ちょっと難しかった。まずまずだよ。お前は？」←この反応はおそらく謙遜

じゅん「3で割った余りは２だったよ」

ライバル「そ、そうか」

じゅん「そっちは？３で割った余りはいくつだった？」

↑自分から先に情報を開示することによって相手の情報を引き出しやすくしている

　　（これを心理学で返報性の法則といいます。

　　　結構使えるので覚えておいて損はないでしょう）

ライバル「１だね」

じゅん「５で割った余りは？」

ライバル「２かな」

↑一度答えた質問には次も答えやすいものです。

　　重要な取引を行う際は、本題に入る前に軽めの話題について相手からの同意を得ておきましょう

じゅん「なら、７で割った余りは？」

ライバル「６だけど、それがどうしたんだ？」

じゅん「どうもしないさ」クールにその場を去る

じゅん（９７点、だと！？）あくまでもクールな雰囲気を貫く

～～～～～～～～～～～～～

寸劇にお付き合いいただきありがとうございます。

早速本題の解説に移りましょう。

いま、ライバルのテストの点を求めたいので、

未知数で置きます。

ライバルの点を$x$としましょう。

３で割った余りが１とのことなので、

$x \equiv 1(\mod 3)$

です。

同様に、

$x \equiv 2 (\mod 5)$

$x \equiv 6 (\mod 7)$

となります。

これらをまとめると、

\[ \left\{ \begin{array}{ll} x\equiv 1 && (\mod 3) \cdots ①\\ x\equiv 2 && (\mod 5)\cdots ② \\ x\equiv 6 && (\mod 7) \cdots ③ \end{array} \right. \]

という３つの式の連立一次合同式を解けばよいことが分かります。

①より、$x-1=3k_1\cdots ①’$

②より、$x-2=5k_2\cdots ②’$

③より、$x-6=7k_3\cdots ③’$

($k_1, k_2, k_3$は整数)

となります。

連立方程式の最も基本的な解き方は、

文字消去です。

中学校では、文字消去の手段として代入法と加減法を習います。

今回は基本的に代入法を採用していきますが、

合同式なので、法の数を上手く選ぶことでも文字を消せます。

（例えば、３を法とする世界では、３の倍数を係数に持つ文字は消せます）

いかに文字消去してシンプルな一次不定方程式に持ち込むか、

という発想で式を整理していきます。

①’より、

$x=3k_1+1$

です。

②’より、

$x=5k_2+2$

です。ここから代入法で文字消去しましょう。

$x$を消去すると、

$3k_1+1=5k_2+2$

です。

よって、

$3k_1=5k_2+1$

となります。

これを法を３として考えると、（５でもいいですが）

$0\equiv 2k_2+1 (\mod 3)$

となり、一文字消せました。

移項すると、

$2k_2\equiv -1 (\mod 3)$

です。

マイナスの数は嫌なので、両辺に３を足しましょう。

$2k_2+3 \equiv -1+3 (\mod 3)$

$2k_2+0 \equiv 2 (\mod 3)$

$2k_1 \equiv 2 (\mod 3)$

幸運にも２と３は互いに素なので、合同式の割り算を実行できます。

$k_2 \equiv 1 (\mod 3)$

よって、

$k_2=3k_4+1$　$(k_4)$は整数

となります。

これを②’に代入しましょう。

$x=5(3k_4+1)+2$

$x=15k_4+7$

ここで、③’より、

$x=7k_3+6$

先ほどと同じように$x$を消去すると、

$15k_4+7=7k_3+6$

$15k_4+1=7k_3$

係数が１桁の文字より、２桁の文字が消えた方が嬉しいので、

１５を法として考えます。

すると、

$0+1 \equiv 7k_3 (\mod 15)$

となり、

$7k_3 \equiv 1 (\mod 15)$

です。

したがって、

$7k_3-1=15k_5$　$(k_5)は整数$

となり、

$7k_3-15k_5=1$

を解けばよいことになります。

これは普通の一次不定方程式なので、まず特殊解を見つけましょう。

ユークリッドの互除法を使うまでもなく、

$k_3=-2, k_5=-1$

が解の一つと分かるので、

$7k_3-15k_5=1$から

$7×(-2)-15×(-1)=1$

を引き算しましょう。

$7(k_3+2)-15(k_5+1)=0$

$7(k_3+2)=15(k_5+1)$

７と１５は互いに素なので、

$k_3+2=15n$

$k_5+1=7m$　$(m, n)$は整数

となります。

$k_3=15n-2$を③’に代入しましょう。

$x=7(15n-2)+6$

$x=105n-8$

$x$はテストの点数なので、

$0≦x≦100$です。

これを満たす$n$は$n=1$のときで、

$x=97$

とテストの点を求めることができます。

めでたしめでたし、

とはいきませんよね。

おいおい、

こんな複雑な計算を暗算できる奴がどこにいんだよ！！

と思ったことでしょう。

そう。

ライバルとの会話の中でこんな計算はしていません。

簡略バージョンの方法を次の見出しで紹介します。

連立一次合同式の解法（簡略バージョン）

先ほどは、ライバルのテストの点を求めるために

\[ \left\{ \begin{array}{ll} x\equiv 1 && (\mod 3) \cdots ①\\ x\equiv 2 && (\mod 5)\cdots ② \\ x\equiv 6 && (\mod 7) \cdots ③ \end{array} \right. \]

を立式し、うまく文字消去して一次不定方程式に持ち込みました。

結構計算は複雑でした笑

でも、会話の中でこんな計算をしている余裕があるはずがありません。

実際は

７０×１＋２１×２＋１５×６＝２０２

$202 \equiv 97 (\mod 105)$

という計算でテストの点を求めています。

なんと２行です。

なんでこんな簡略化ができるのか？

そのカギは７０，２１，１５という３つの数が握っています。

もともとの連立一次合同式は

\[ \left\{ \begin{array}{ll} x\equiv 1 && (\mod 3) \cdots ①\\ x\equiv 2 && (\mod 5)\cdots ② \\ x\equiv 6 && (\mod 7) \cdots ③ \end{array} \right. \]

でした。

法となっている数は、上から順に３，５，７です。

ここで、

７０は３で割った余りが１で、５，７で割った余りが０です。

２１は５で割った余りが１で、３，７で割った余りは０です

１５は７で割った余りが１で、３，５で割った余りは０です。

$x\equiv 1 (\mod 3)$は、

３で割った余りが１であることを要求する条件なので、

７０を１個配置して処理します。

次に、

$x \equiv 2(\mod 5)$は、

５で割った余りが２であることを要求する条件なので、

２１は１個ではなく２個配置することになります。

同様に、

$x \equiv 6(\mod 7)$

は７で割った余りが６であることを要求するので、

１５を６個配置して処理しましょう。

こうして、

７０×１＋２１×２＋１５×６

という式が立式されます。

ここでワンダフルなのは、

例えば７０は３で割った余りの情報だけを含んでおり、５，７で割るとあまり０なので、

５で割った余りの情報を担当している２１の邪魔をしない、という点です。

７０，２１，１５はぞれぞれの担当する余りの情報だけを処理し、

他の部署に越権行為をすることなく己の職務をわきまえているのです。

なるほど、７０．２１．１５がすごいことは分かった。

で、そいつらはどうやって求めるの？

という疑問が残ると思いますので、続きを解説します。

７０が満たすべき条件は、

「３で割った余りが１であり、５，７で割った余りは０である」

となります。あとは、この条件を満たす数を求めればよいです。

$5×7x\equiv 1(\mod3)$

を解いて$x$を求めると、

$5×7x$がこの条件を満たすことが分かると思います。

したがって、

$5×7x-1=3k$　$(kは整数)$

となり、一次不定方程式

$5×7x-3k=1$

を解けばよいことになります。

$5×7$と$3$は互いに素なので、

この一次不定方程式は解くことができ、

例えば$x=2, k=23$とすると、

$5×7x=5×7×2=70$

となり、７０が求まります。

のこりの２１と１５も同様です。

最後に、

７０×１＋２１×２＋１５×６＝２０２

ですが、２０２はテストの点の最大値１００を超えてしまっているので、

１０５を法として２０２と合同かつ０～１００に収まる値を求めて、

テストの点は９７点であるという結論を得ています。

１０５はどこから出現したのでしょう？

それは、$\mod 3, \mod 5, \mod 7$

が関わっています。

３，５，７の最小公倍数が１０５なのです。

以上をまとめると、次のようになります。

余談ですが、最初の寸劇でライバルからテストの点を３，５，７で割った余りを聞いていましたが、

なんで３，５，７をチョイスしたの？

という理由も紹介しておこうと思います。

テストは１００点満点なので、たとえば１０１（素数）で割った余りでもよいわけですが、

これだと直接テストの点を聞いているのと変わりません。

そうとばれないような小さい数で、かつ積を取ったときに１００を超えるような

数たちを選ぶ必要があります。

で、１００，１０１，１０２，１０３…を順に素因数分解していくと、

１０５＝３×５×７で、しかも３，５，７はどれも互いに素という

超いい感じの手ごろな数が見つかり、これが採用されたわけです。

（例えば１００＝２×２×５×５で、同じ数が何回も出てくるので不都合です）

そして、これを文字に置き換えて一般化すると、次のような予想が得られます。

これを中国剰余定理（式３つバージョン）と言います。

古代中国の「孫子算経」という書物に載っていた定理ゆえに中国剰余定理と呼ばれるようになったそうです。

今回は実際の計算方法の解説に重きを置きましたので、

証明はまた別の記事で行おうと思います。

まとめ

いかがでしたか？

ライバルのテストの点が知りたいけど恥ずかしくて聞けないときに

ご活用ください。

また、今回はテストの点を扱いましたが、

同じノリで年齢を当てることもできますので、

こちらも機会があればぜひ使ってみてください。

（１０５歳以上のお方については、法としてチョイスする数を変える必要がありますが）

・テストの点は、連立一次合同式で解ける

・連立一次合同式は、一次不定方程式で解ける

・簡略バージョンの解法だと、２行で解ける

・結論を一般化すると、中国剰余定理が出現

以上を押さえてくださればと思います。

なお、中国剰余定理の証明については、別の記事で解説しますので、

ご期待ください。

ではまた次の記事でお会いしましょう！