実践演習 整数系

下二桁の扱い【4乗数に関わる下二桁】【完全剰余系】【2007年度 東京大学ほか】

問題1はこちら(画像をクリックするとPDFファイルで開きます。)

問題2はこちら(画像をクリックするとPDFファイルで開きます。)

下二桁の数についてスポットを当てた問題を東大、京大から2題セレクトしました。

扱っている題材は下二桁という点で共通していますが、オチについてはそれぞれ違う味わいの問題です。

味比べするのも一興です。

(以下ネタバレ注意)

 

+ クリック(タップ)して続きを読む

問題1について

問題1はこちら(再掲)(画像をクリックするとPDFファイルで開きます。)

まず、10進法における下二桁の数は

\(100\) で割った余り

という見方をします。(ここをクリアーできないと身動きがとれないでしょう。)

手なりに考えると

\(100\) で割った余りを考えるにあたり

  • \(m=100M+r\) ( \(0 \leq r \leq 99\) )
  • \(m=100M+10a+b\)

などと設定したくなる気持ちは十分分かります。

ただこの後、\(5m^{4}\) を考えるにあたっては少し億劫です。

少し工夫

この後、4乗計算をするのであれば、

\(m=10a+b\)

と設定すれば十分でしょう。

実際にどのような計算になるかについては【解 1】をご覧ください。

なお、手なりに

  • \(m=100M+r\) ( \(0 \leq r \leq 99\) )
  • \(m=100M+10a+b\)

と設定しても合同式などを駆使しながら、

100の倍数となっている部分は無視する

という態度でいけば、十分完答が狙えます。

これについては【解 2】で触れてあります。

問題1の解答はコチラ

問題2について

問題2はこちら(再掲)(画像をクリックするとPDFファイルで開きます。)

大枠の意識として、10進法における下二桁の数は

\(100\) で割った余り

という見方をする点は、問題1と同じです。

(1) について

合同式で考えると明確です。

以下、合同式の法は \(100\) とします。

\(nx \equiv ny\)

\(nx-ny \equiv 0\)

\(n(x-y) \equiv 0\)

なので、整数 \(M\) を用いて

\(n(x-y)=100M\)

と表せます。

\(n\) は素因数 \(2\) も \(5\) ももたないことから、\(n\) と \(100\) は互いに素です。

したがって、\(x-y\) が \(100\) の倍数ということになり、

\(x-y \equiv 0\) ,  すなわち

\(x \equiv y\)

が得られ、解決です。

(2) について

(1) の対偶

\(C(x) \neq C(y)\) ならば \(C(nx) \neq C(ny)\)

を考えてみるとクリアーに見えます。

日本語で見ると

日本語での翻訳

下二桁が異なっているならば、それらを \(n\) 倍しても下二桁は異なる

ということです。

別にこれらは2個の数に限らない主張で、

\(C(0)\) ,  \(C(1)\) ,  \(C(2)\) ,  \(\cdots\) ,  \(C(99)\)

という \(100\) 個の数に対して

\(C(0)\) ,  \(C(n)\) ,  \(C(2n)\) , \(\cdots\) ,  \(C(99n)\)

は全て異なる

ということも言えます。

これら \(100\) 個の数は全て異なり、「重複や漏れがない」状態ですから、

\(C(0)\) ,  \(C(n)\) ,  \(C(2n)\) , \(\cdots\) ,  \(C(99n)\)

のどれかが \(1\) となっているわけです。

これは、\(C(xn)=1\) となる \(x\) の存在を意味していますから、証明完了と言うことになります。

問題2の解答はコチラ

 

ウンチク

興味のある方はどうぞ

+ 興味のある方はクリック(タップ)して続きを読む

今回問題2の議論の進め方は、初見だと高尚に見えるかもしれません。

この世の全ての整数を「何かで割った余り」で分類することを考えます。

例えば、世の中の整数を \(7M+r\) と表現したとき、

\(7M\) ,  \(7M+1\) ,  \(7M+2\) ,  \(7M+3\) ,  \(7M+4\) ,  \(7M+5\) ,  \(7M+6\)

として分類することが必要十分です。

(どれが足りなくてもダメですし、これだけあれば他にはいらないということです。)

この7つあるグループを \(7\) を法とした剰余類と言います。

ただ、分類の仕方はこれだけではありません。

例えば世の中の整数を

\(7M-3\) ,  \(7M-2\) ,  \(7M-1\) ,  \(7M\) ,  \(7M+1\) ,  \(7M+2\) ,  \(7M+3\)

と分類して表現することもできます。

\(7M-1\) と表現できる数は \(7\) の倍数から見て \(1\) 足りない連中ですから、\(7M+6\)  と表現できる数と同じグループに属すことになります。

これら7つのグループも \(7\) を法とした剰余類です。

つまり、剰余類のとり方というのは一意的ではないということです。

この \(7M+r\) における \(r\) の部分を「代表元」などと呼んだりします。

通常は「余り」を代表元とすることが多く、それが一般的です。

ここから先はこの代表元だけを取り出して

\(\{0 \ , \ 1 \ , \ 2 \ , \ 3 \ , \ 4 \ , \ 5 \ , \ 6\}\)

\(\{-3 \ , \ -2 \ , \ -1 \ , \ 0 \ , \ 1 \ , \ 2 \ , \ 3\}\)

といった集合を考えます。

これらは先ほども述べた通り、世の中の整数を \(7M+r\) という形で分類するための \(r\) としての必要十分な集合です。

これらを

法を \(7\) とした完全剰余系

と言います。

完全剰余系の中で、法 \(7\) と互いに素なものを要素にもつ集合を

既約剰余系

と言います。

例えば、

\(\{0 \ , \ 1 \ , \ 2 \ , \ 3 \ , \ 4 \ , \ 5 \ , \ 6\}\)

は完全剰余系で、

\(\{1 \ , \ 2 \ , \ 3 \ , \ 4 \ , \ 5 \ , \ 6\}\)

は既約剰余系です。

このあたりの話題の議論の進め方は独特なものがあります。

今回の問題2以外にも、慣れておきたいという方は

フェルマーの小定理【2項定理からのアプローチ】【2011年度 関西大学】

2020/12/15    ,

問題はこちら(画像をクリックするとPDFファイルで開きます。)   フェルマーの小定理 \(p\) を素数 , \(a\) を任意の自然数とするとき \(a^{p} \equiv a\)  ...

不定方程式の整数解とその発展【ベズーの補題】【2000年度 大阪大学ほか】

2021/6/30    

例題はこちら(画像をクリックするとPDFファイルで開きます。) \(a\) , \(b\) , \(c\) を整数として \(ax+by=c\) という形の不定方程式(ディオファントス方程式)の整数解 ...

でも、具体的な問題を通じて触れてあります。

-実践演習, 整数系
-,

© 2022 MathClinic