というわけでなぜかこんな話題。数学の話題としては代数学の知識で解答できるので例題から。いわゆるあまりに関する問題です。

Q. 7で割ると3あまり、11で割ると5あまり、13で割ると4余る数は1から1000までの間に何個あるか答えなさい

似たような問題はほかにも作れます。たとえば

Q. 4で割ると1あまり、7で割ると4あまる数は1から400までの間に何個あるか答えなさい

のようなものです。小学生向けの問題として出てくることも多そうな問題ですが・・・。

問題の一般系はこんな感じ

一般化するとこの問題に共通する前提条件を書かなければならないので解法がわかりやすくなります。上記の問題の一般系はこんな感じですね。

x₁で割るとr₁あまり、…、x_nで割るとr_nあまる数は0からmまでの間に何個あるか答えなさい。ただし、x₁からx_nは互いに素とする。

このときに重要なのは一般化することで現れた条件「ただし、x₁からx_nは互いに素とする」が鍵になります。この条件があるととある定理が使えるため簡単な解答となるわけです。ちなみに「互いに素」の意味がわからない人であれば「どの2個に対しても最大公約数は1となる」とすれば小学生でもわかると思います。

一般化した問題の解答は？

こんな感じになります。中学生以下だと読み取るのは難しい回答かも。

中国剰余定理よりx=x₁×x₂×…x_nとするとき、0からx-1までには対象となる数はただ一つ存在する。この数をyとするとき、問題の状態に当てはまる数はlx+y(ただしlは正の整数)の形となる。よって、m=qx+r(ただし、qとrは整数であり0<=r<xを満たすものとする)となるとき、y<=rであるときには対象の数はq+1個存在し、そうでないときには対象の数はq個存在する。

中国剰余定理を使うとこんな感じの解答になります。数え始める数を0にしてあるおかげで意外ときれいな解答になりました。

で、例題の解答ですが

それはこんな感じ。はじめの問題では

Q. 7で割ると3あまり、11で割ると5あまり、13で割ると4余る数は1から1000までの間に何個あるか答えなさい

A. 7×11×13=1001であり、7、11、13は互いに素だから中国剰余定理より0～1000までに対象の数は一つ存在する。0はすべての数であまりが0となるが問題文よりそれはあり得ない。よって1から1000までの間には1個のみ存在する。

後の問題では

Q. 4で割ると1あまり、7で割ると4あまる数は1から400までの間に何個あるか答えなさい

A. 4×7は28であり、4と7は互いに素だから中国剰余定理より0～27までに対象の数は一つ存在する。これを拡張すると400÷28=14…8となることに注意すると、まず問題文より0はあり得ない。同様に1～8までで考えるとどの数も問題文の条件には当てはまらない。よって28×14=392から28×14+8=400までには対象の数は一つも存在しない。よって1から400までの間には14個存在する

となります。中国剰余定理を用いるとこの手のあまりに関する問題があっさり解けてしまうのが面白いところですね。

Tweet