今回は2021を盛り込んだ整数問題です.今年出題された6問の中でも最も面白い問題です.
問題
以下の問いに答えよ。
正の奇数 , と正の整数 , が を満たしているとする。 を で割った余りが を で割った余りに等しいならば, を で割った余りは を で割った余りと等しいことを示せ。
正の整数 , が を満たしているとする。このとき,, に対して となるような正の整数 , が存在することを示せ。
, は (2) の通りとし,さらに が の倍数で割り切れるとする。 を で割った余りは を で割った余りと等しいことを示せ。
を で割った余りを求めよ。
解答解説
この問題は誘導が良く設計されています.多分,全6問の中で一番面倒な問題であったと思います.が,私はこういう問題の方が得意なので,戦略はすぐにたちました.とはいえ,解答を書くとなると話は別です.
実際,(2) と (3) については長くなってしまったために解答を書き換えました.(オリジナルは感想の後に載せています.)
(1) の解答
この問題は素直に考えましょう.
, を で割った商をそれぞれ , , 共通の余りを とおくと,
と表すことができます.ここで, と は奇数であり, は , を で割った余りであるので, もしくは となります.
より すなわち となりますが,, , , , は全て整数であることから,右辺は 4 の倍数で, と は互いに素であるので, は4の倍数となります.
すなわち, を で割った余りと を で割った余りは等しいことが証明されました.
(2) の解答
を式変形していきます.
ここで, という見慣れぬ記号が出てきますが,これは の掛け算版です.この記号を使う方が書くのが簡単で,どのように分子分母を分けたかが分かりやすいので使いました.
上の式は要するに,分子分母にある因数(掛け算の構成要素)を「 の倍数」「 の倍数ではない偶数」「奇数」に分けて, の倍数同士を で,の倍数ではない偶数同志を で約分しています.
これにより,
とおくと, と はそれぞれ奇数であり,上式より すなわち が成立するのは明らかなので,これが条件を満たす と になります.
(3) の解答
を で割った余りと を で割った余りが等しければ,(1) より命題が成立することになります.
, が整数であるとき,
したがって,奇数のみからなる積は,積に含まれる で割って 余る因数の個数が偶数のときは で割って 余り,奇数のときは で割って 余ります.よって, に含まれる で割って 余る因数の個数と に含まれる で割って 余る因数の個数の偶奇が等しいことを証明すれば十分となります.
では、 と の因数の中に で割って 余る数が何個あるかを数えましょう.
を で割った余りは と交互に現れることから,自然数 に対して の中には で割って 余る数が 個存在します.ここで, は を超えない最大の整数を表します.
以上のことから, で割って 余る数の個数は次のようになります:
- の中には 個
- の中には 個 ( は の倍数より)
- の中には 個
- の中には 個
- の中には 個
- の中には 個
したがって, と の中の で割って 余る因数の個数をそれぞれ と で表すと,
となるので, となります.ここで, は の倍数であることより, と の偶奇は一致するため, となります.したがって, すなわち となり, と の偶奇も一致したため,命題が証明されました.
(4) の解答
単に計算問題です.
であるので,余りは となります.
感想
小問 (2) と (3) は当初の証明から変更しました.アイデアは同じですが,上記のように と を直接求める方が記述が簡単になるからです.
ですが,当初の証明の方が私の思考が伝わると思うので,かなり恥ずかしい代物ですが敢えて残しておきます.
しかし,この問題は入試としてはかなりタフだと思います.特に (3) は時間内で解くのが厳しい.(1), (2), (4) くらいが限界のような気がします.
問題としてはなかなかに意欲的で,面白い問題だと思います.少し泥臭いことを要求しますが,このくらいはありだと思いますし,それほど汚い感じはしませんでした.
別解(当初の証明)
(2) の解答
と が因数として をいくつ持つかを数えれば終わりです.
と表すとします.ここで,, は非負整数で,, は正の奇数であるとします.このとき, = が成立すれば が成り立つので,以下では と に含まれる 因数 の個数が等しいことを示します.
自然数 に対して に含まれる因数 の個数を とします.このとき,次の補題が成り立ちます.
は奇数であるので, は明らかです. の中で因数 を含むのは偶数である のみで,これらすべてを で割ると が得られます.したがって, ~ までの中に含まれる因数 の個数 に,各偶数から 個ずつ取り除いた因数 の個数の合計 を加えた数が になります.
ここで、
であるので、 に含まれる因数 の個数 , に含まれる因数 の個数 となりますが,補題1より
であるので,
が成立し, が証明されました.
(3) の解答
前問より かつ であることが示されたので,(3) では に含まれる ( に含まれる) 因数で で割って 余る数の個数と, に含まれる( に含まれる) 因数で で割って 余る数の個数を数えます.ただし、その偶奇だけが等しければ十分です.
というのも,つの奇数をかけるとき, で割った余りの組合せは , , , の 通りありますが, と のときは積を で割ると余りが となり, と のときは積を で割ると余りが となります.
ということは,奇数因数の積を で割るとき, で割って余りが である因数が偶数個であれば余りが に,奇数個であれば余りが になります.また,割り算に関しても同様です.
小問 (2) と同じように に含まれる で割って 余る奇数因数の個数の偶奇を で表します.このとき,次の性質が成り立ちます.
任意の正の整数 に対して
ここで, は を超えない最大の整数とします.
を偶奇で分けます.
偶数部分 に含まれる奇数因数は,これらを で割った に含まれる奇数因数と等しいため,この中で で割って 余る奇数因数の個数の偶奇は に等しくなります.
一方,奇数部分 は で割ると となるので,余りが となる個数は となります.
よって, の式は正しいことが示されました. も同様です.
に含まれる で割って 余る因数の個数の偶奇は , に含まれる で割って 余る因数の個数の偶奇は であるので,以下では
であることを示します.
補題 2 より
となるので,
ここで, が の倍数であるので, かつ となり,
となります.
したがって, と を で割った余りは等しいので, と も で割った余りが等しいことが証明されました.