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

ライバルのテストの点を暴け!

数学のテスト。

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

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

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

目次

連立一次合同式の解法

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

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

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

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

テストの点を3,5,7で割った余りがそれぞれいくつか聞いてみましょう。

~寸劇~

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

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

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

ライバル「そ、そうか」

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

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

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

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

ライバル「1だね」

じゅん「5で割った余りは?」

ライバル「2かな」

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

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

じゅん「なら、7で割った余りは?」

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

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

じゅん(97点、だと!?)あくまでもクールな雰囲気を貫く

~~~~~~~~~~~~~

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

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

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

未知数で置きます。

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

3で割った余りが1とのことなので、

$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. \]

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

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

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

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

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

となります。

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

文字消去です。

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

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

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

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

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

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

①’より、

$x=3k_1+1$

です。

②’より、

$x=5k_2+2$

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

$x$を消去すると、

$3k_1+1=5k_2+2$

です。

よって、

$3k_1=5k_2+1$

となります。

これを法を3として考えると、(5でもいいですが)

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

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

移項すると、

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

です。

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

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

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

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

幸運にも2と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$

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

15を法として考えます。

すると、

$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)$

7と15は互いに素なので、

$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. \]

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

結構計算は複雑でした笑

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

実際は

70×1+21×2+15×6=202

$202 \equiv 97 (\mod 105)$

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

なんと2行です。

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

そのカギは70,21,15という3つの数が握っています。

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

\[ \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. \]

でした。

法となっている数は、上から順に3,5,7です。

ここで、

70は3で割った余りが1で、5,7で割った余りが0です。

21は5で割った余りが1で、3,7で割った余りは0です

15は7で割った余りが1で、3,5で割った余りは0です。

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

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

70を1個配置して処理します。

次に、

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

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

21は1個ではなく2個配置することになります。

同様に、

$x \equiv 6(\mod 7)$

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

15を6個配置して処理しましょう。

こうして、

70×1+21×2+15×6

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

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

例えば70は3で割った余りの情報だけを含んでおり、5,7で割るとあまり0なので、

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

70,21,15はぞれぞれの担当する余りの情報だけを処理し、

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

なるほど、70.21.15がすごいことは分かった。

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

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

70が満たすべき条件は、

「3で割った余りが1であり、5,7で割った余りは0である」

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

$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$

となり、70が求まります。

のこりの21と15も同様です。

最後に、

70×1+21×2+15×6=202

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

105を法として202と合同かつ0~100に収まる値を求めて、

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

105はどこから出現したのでしょう?

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

が関わっています。

3,5,7の最小公倍数が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$が存在し、$0≦x≦105-1$の範囲では97ただ一つであった。

余談ですが、最初の寸劇でライバルからテストの点を3,5,7で割った余りを聞いていましたが、

なんで3,5,7をチョイスしたの?

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

テストは100点満点なので、たとえば101(素数)で割った余りでもよいわけですが、

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

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

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

で、100,101,102,103…を順に素因数分解していくと、

105=3×5×7で、しかも3,5,7はどれも互いに素という

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

(例えば100=2×2×5×5で、同じ数が何回も出てくるので不都合です)

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

$n_1, n_2, n_3$が、どの2つをとっても互いに素な自然数であるとする。

このとき、任意の整数$a_1, a_2, a_3$に対して、

\[ \left\{ \begin{array}{ll} x\equiv a_1 && (\mod n_1) \\ x\equiv a_2 && (\mod n_1) \\ x\equiv a_3 && (\mod a_3) \end{array} \right. \]

を満たす整数$x$が$0≦x≦n_1n_2n_3-1$の範囲にただ一つ存在する

これを中国剰余定理(式3つバージョン)と言います。

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

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

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

まとめ

いかがでしたか?

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

ご活用ください。

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

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

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

(105歳以上のお方については、法としてチョイスする数を変える必要がありますが)

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

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

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

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

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

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

ご期待ください。

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

ブログランキング参加してます

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

CAPTCHA


目次