余り-整数問題 | 余りが等しいことを高校の数学の形で
「 余り 」が等しいということの証明が、高校数学の整数問題で出題されるときがあります。「余りが等しい」ことの定義が、高校の数学から使用されます。
算数のときから使っていた定義に当てはまっても、もちろん余りが等しいということになります。
ここで、高校の論理の同値という考え方が大切になります。
数学では、同値である条件を書き換えることができ、状況に応じて扱いやすい方で議論を進めます。
高校の数学から使う「余りが等しいことの定義」は、文字式を利用した証明を作成するときに使いやすいです。
ただ、算数から使っている余りの定義の意味での「余りが等しい」ということが同値であることを厳密に証明することは、とても難しいことになります。
高校数学の整数分野を学習するときには、同値であることを認めて学習を始め、理解が深まってきたら厳密な証明を眺めてみるくらいが良いかもしれません。
まず、余りの定義から確認します。
余り-整数問題 :算数の定義から書き換え
【算数の余りの定義】
割られる数 = 割る数 × 商 + 余り
※ 商は整数とする。
※ 余りは「割る数 － 1」であり、 0 以上の範囲にある整数である。
※ 割る数は 1 以上の整数（自然数）。
※ 検算（確かめ算）の式です。
実際に、余りの定義に基づき、17 を 5 で割ったときの余りを求めてみます。
割られる数が 17 で、割る数が 5 なので、
17 = 5 × 3 + 2 という検算の形の等式が得られます。
商は 3 という整数で、余りとなる整数 2 は、5 － 1 以下であり、0 以上となっています。
この算数で学習をした余りを定義している等式に当てはまったら、余りが確定するということになります。
ただ、割る数を一定の自然数で固定して考えているときに、この算数で学習をした余りの定義と見た目が違っても、算数の余りの定義を満たす整数となっているときがあります。
そこで、次の定義があります。
【高校からの余りが等しい定義】
割る数を自然数 k として固定しているとき、二つの整数 a と b について、(a － b) が k の倍数であるとき、a を k で割った余りと b を k で割った余りが等しい。
※ 合同記号を使うと a ≡ b (mod k)
二つの整数 a と b、そして割る数である自然数 k について、【高校からの余りが等しい定義】に当てはまっていたとします。
このときに、a と b を【算数の余りの定義】の内容の等式における余りが等しくなっています。
逆に、二つの整数 a と b、そして割る数である自然数 k について、【算数の余りの定義】において、a を k で割った余りと b を k で割った余りが等しいときを考えます。
このときに、必ず【高校からの余りが等しい定義】に該当します。
数学の論理でいう同値ということになります。本当に同値となっているのかということを厳密に証明するのは、難しいです。一気に難関レベルの大学受験の記述証明の内容となります。
そこで、このブログ記事では、同値になっているということを前提として、以下で議論を進めていきます。
※ ユークリッド整域という大学数学の記事で、確かに同値となっていることを厳密に証明しています。
この記事では、厳密証明は置いておいて、シンプルな例で、「余りが等しい」ということについて様子を見てみます。
【具体例で試してみる】
割る数を自然数 6 として、二つの整数 33 と 15 について、余りが等しいかどうかを確認してみます。
まず、先ほどの【高校の余りが等しい定義】に当てはまっているかをチェックしてみます。
33 － 15 = 18 で、18 は 6 の倍数です。
そのため、33 － 15 が 6 の倍数となっているので、高校の数学でいうところの余りが等しいということになります。
【高校の余りが等しい定義】に当てはまっているわけですが、【算数の余りの定義】の式（検算の式）にしたときに、余りの部分が同じ整数となっているのかを確認してみます。
33 も 15 も、6 で割ったときの余りが 3 です。
これで、算数の定義の意味でも、余りが等しいということになります。
今度は、逆についても具体的に確認してみます。算数の余りの定義で、余りが表示されていたとします。
33 = 6 × 5 + 3,
15 = 6 × 2 + 3
このとき、
辺々引くと、33 － 15 = 6 × 3
6 × 3 は、6 の倍数ということですから、33 － 15 は 6 の倍数ということです。これは、【高校の余りが等しい定義】に当てはまっています。
以上の内容をまとめます。
余りが等しいことの確認方法
【確認方法 1】
算数の余りの定義の検算の形にして、余りが等しいかどうかを確認する。
※ 余りについての範囲が決め手になることが多いです。
【確認方法 2】
高校の余りが等しいことの定義に当てはまっているかどうかを確認する。
確認方法が二つあります。先ほど述べたように、どちら確認しても論理的に同じ結果ということです。
しかし、状況によっては、どちらかが困難で、もう片方のほうがスムーズに余りが等しいということを確認できるときがあります。
どちらの確認方法の方が優れている、劣っているということではなく、状況に応じて判断することが整数問題において大切になります。
余り-整数問題 :余りが等しいことの証明
整数分野の証明を行うときに、中学の数学で学習した倍数（もしくは約数）の表し方が大切になります。
二つの整数 x と y について、x が y の倍数である（y が x の約数である）とは、
ある整数 z を用いて、x = yz と表すことができることです。
これは、先ほどの検算において、余りが 0 ということです。
約数の方で考えると、x を y で割ったときの商が z で余りが 0 ということです。
※ 式で表すと、x = yz + 0
0 を足しても値は変わらないので、x = yz としています。
具体的な証明の実践
【命題 1】
割る数を自然数 k とし、整数 x と y について、x を k で割ったときの余りと y を k で割ったときの余りが等しかったとします。
このとき、どんな整数 t に対しても、
x + t を k で割った余りと y + t を k で割った余りは等しくなります。
合同記号を使うと、x ≡ y (mod k) であるときに、どんな整数 t に対しても x + t ≡ y + t (mod k) ということです。
x － y が k で割り切れるときに、x ≡ y (mod k) と表すということです。
これは、合同記号についての性質を示す内容になりまして、【高校の余りが等しい定義】で証明を進めていく方が、楽に議論を進められます。先ほどの【確認方法 2】の方です。
そうすると、結論は (x + t) － (y + t) という整数が k の倍数となるということを示せば良いということになります。
＜証明＞
x を k で割ったときの余りと y を k で割ったときの余りが等しいという仮定から、
【高校の余りが等しい定義】より、
x － y = ks (s は整数) と表すことができます。
一方、(x － t) － (y － t) = x － y より、
(x － t) － (y － t) = x － y = ks
s は整数なので、(x － t) － (y － t) は k の倍数、
すなわち、(x － t) － (y － t) は k で割り切れるということを意味しています。
【高校の余りが等しい定義】を満たしたので、x － t を k で割ったときの余りと y － t を k で割ったときの余りは等しいということになります。【証明完了】
算数の余りの定義の検算の形にして、余りが等しいかどうかを確認するという方法でも、今回の【命題 1】を証明することができます。
ただ、【高校の余りが等しい定義】で議論を進めた方が、この【命題 1】の証明については楽です。
どちらで示しても、k で割ったときの余りが等しいということが分かっていると、状況に応じて使い分けをして効率よく証明を進めることができます。
数学では、既に証明した命題を適用するということができます。次の【命題 2】は、【命題 1】をうまく利用することで証明ができます。
また、数学では、背理法という証明論法があります。次の【命題 2】の証明で背理法を使います。
証明した命題を利用
【命題 2】
k を自然数とし、x と y と r を整数とします。
このとき、「x を k で割ったときの余りと、y を k で割ったときの余りが異なる」ならば、
「x + r を k で割ったときの余りと y + r を k で割ったときの余りは異なる」。
自然数 k で整数 x + r と整数 y + r を割ったときに、「余りが等しい」か「余りが等しくない」かのいずれか一方のみが成立します。
こういう状況で、「余りが等しい」とすると矛盾が出るということを示すと、背理法という証明論法から、もう一方の「余りが等しくない」という結果が導かれます。
＜証明＞
自然数 k で整数 x + r と整数 y + r を割ったときの余りが等しいと仮定します。
【高校の余りが等しい定義】より、
(x + r) － (y + r) は 自然数 k で割り切れるので、
(x + r) － (y + r) = ks (s は整数) と表すことができます。
ここで、(x + r) － (y + r) = x － y なので、
x － y = (x + r) － (y + r) = ks
よって、x － y が k の倍数ということになります。
これは、【高校の余りが等しい定義】より、x を k で割ったときの余りと y を k で割ったときの余りが等しいということになります。
しかし、「x を k で割ったときの余りと、y を k で割ったときの余りが異なる」ということだったので、これは矛盾です。
以上から、背理法より、「自然数 k で整数 x + r と整数 y + r を割ったときの余りは異なる」ということになります。【証明完了】
この【命題 2】は、「x を k で割ったときの余りと、y を k で割ったときの余りが異なる」ときに、「x と y にともに同じ整数 r を加えてから k で割っても、やはり余りは異なる」ということを示しています。
余りが等しいということを直感的に考えると、よく分からない内容ですが、文字を用いて定式化して扱うと、すぐに証明ができてしまいます。
次に、難関大学の記述証明レベルの内容を扱います。今の【命題 2】とともに、中国剰余定理の内容に深く関わってくる内容が後に証明をする【命題 4】です。
※ この定理の証明はリンク先の記事に書いています。
また、大学数学の代数分野の内容を学習するときにも、良い下準備になってくれます。
余り-整数問題 :難しい証明問題
【命題 3】
a を 0 ではない整数で、自然数 k との最大公約数が 1 とします。
このとき、整数 x と y について、「ax を k で割った余りと ay を k で割った余りが等しい」ならば、「x を k で割った余りと y を k で割った余りが等しい」です。
＜証明＞
x = y のときは、「x を k で割った余りと y を k で割った余りが等しい」ので命題は成立します。
そのｔめ、以下において x ≠ y として議論を進めます。
S = {r | r と r(x － y) ÷ k は整数} という整数全体の部分集合を考えます。
割る数である自然数 k 自身が S の中に含まれています。
※ k(x － y) という整数は、k の倍数だからです。
k は自然数なので、S の中には正の整数が少なくとも 1 つ存在するということになります。そこで、k 以下の自然数であり、かつ S に含まれている自然数の中で最小のものを d とおきます。
※ k 以下の自然数は有限個なので、必ず最小の自然数が存在します。
この d ∈ S について、どんな S の要素も d の倍数となることを示します。
t ∈ S を任意に選びます。t を d で割ったときの余りを r, 商を e とします。
【算数の余りの定義】から、t = de + r
（ただし、整数 r は 0 ≦ r < d － 1 ）
したがって、目指す内容は、余り r が 0 です。
t は S の要素なので、t は整数で、t(x － y) が k の倍数となっています。
そのため、ある整数 p を用いて、
t(x － y) = kp と表すことができます。
また、d ∈ S なので、d(x － y) が k の倍数だから、ある整数 q を用いて、
d(x － y) = kq と表すことができます。
ここで、
r(x － y) = (t － de)(x － y)
= t(x － y) －ed(x － y)
= kp(x － y) － kq(x － y)
= k{p(x － y) － q(x － y)}
ここで、p(x － y) － q(x － y) は整数なので、
r(x － y) は k の倍数ということを意味しています。
よって、r は S に含まれるための条件を満たしたので、r ∈ S となります。
t を d で割ったときの余り r は、
0 ≦ r < d － 1 を満たしていました。
ここで、もし r ≠ 0 とすると、r は自然数となり、d よりも小さい S に含まれる自然数ということになります。しかし、そうだとすると、S に含まれている最小の自然数が d ということに矛盾します。
したがって、r = 0 でなければならないということになります。
すると、t = de となり、t は d の倍数ということになります。
ゆえに、S から任意に要素を選ぶと、必ず d の倍数となっていることが示せました。
ここで、「ax を k で割った余りと ay を k で割った余りが等しい」という仮定から、【高校の余りが等しい定義】より、ax － ay が k の倍数ということになります。
つまり、a(x － y) が k の倍数なので、S に含まれるための条件を a が満たしているので、a ∈ S です。先ほど示した内容から、S に含まれるどの要素も必ず d の倍数でしたから、a は d の倍数ということになります。
よって、d は a の約数となっている自然数です。さらに、a と d の最大公約数が 1 だったので、a の正の約数である d は 1 ということになります。
したがって、1 = d ∈ S です。
この 1 という整数は S の要素なので、1 × (x － y) が k の倍数ということになります。
すなわち、x － y が k の倍数なので、【高校の余りが等しい定義】より、「x を k で割った余りと y を k で割った余りが等しい」ということになります。【証明完了】
この証明では、割ったときの余りが等しいことに関連して、【算数の余りの定義】と【高校の余りが等しい定義】のどちらも状況に合わせて使い分けました。
この S は大学数学の環論で学習するイデアルという条件を満たす特別な整数環の部分集合です。整数環についての理論で、イデアルのどの要素も、そのイデアルに含まれる最小の自然数を倍数になるというものがあります。
イデアルという言葉を使わずに、集合 S の定義だけに関連する内容を出題すると、上の証明のように、高校数学の整数分野の内容で証明ができるときがあります。
そういった意味で、発展内容として難しい大学の整数問題で、イデアルが絡むことがあります。
次の【命題 4】は、示した【命題 3】の対偶になります。その命題が真であれば、対偶命題も真となります。そのために、次の【命題 4】は真です。
対偶も真
【命題 4】
a を 0 ではない整数で、自然数 k との最大公約数が 1 とします。
このとき、整数 x と y について、
「x を k で割った余りと y を k で割った余りが等しくない」ならば、
「ax を k で割った余りと ay を k で割った余りは等しくない」です。
以上の真である命題のうち、【命題 2】と【命題 4】は中国剰余定理の理解において重要な役割を果たします。
この【命題 4】は、余りが等しくないということについての内容で、証明が難しいです。その分、大学で扱う整数論でも役に立ってくれます。
具体的な整数で、【命題 4】の内容を確認しておきます。算数を使った具体例で確認できるのが、このあたりの内容の良いところです。
割る数を 15 として、x = 3, y = 6 のときです。x を 15 で割ったときの余りと、y を 15 で割ったときの余りは異なっています。
15 との最大公約数が 1 である 7 を a として、ax と ay を 15 で割ったときの余りを見てみます。計算しなくても、異なるということが【命題 4】から分かりますが、それを確認してみます。
ax = 21 を 15 で割ったときの余りは 6 です。
ay = 42 を 15 で割ったときの余りは 7 です。確かに異なる余りになっています。
この【命題 4】ですが、割る数との最大公約数が 1 という条件は外せません。最大公約数が 1 でないときには、簡単に反例をつくれます。
割る数を 15 として、x = 0, y = 5 を考えます。x を 15 で割ったときの余りは 0 で、y を 15 で割ったときの余りは 5 なので、異なっています。
a として、3 という 15 との最大公約数が 1 ではない数を考えます。
ax = 0 を 15 で割ったときの余りは 0 です。ay = 15 を 15 で割ったときの余りは 0 です。
よって、ax と ay を 15 で割ったときの余りが一致してしまいました。これは、【命題 4】の結論を否定した結果になってします。
以上から、【命題 4】の a と割る数 k の最大公約数が 1 という条件が必須であることが分かりました。この【命題 4】を使うときには、この最大公約数が 1 という条件に注意です。
フェルマーの小定理の証明にも、この【命題 4】を使います。
余りが等しいか異なるのかということは、合同式を考えるときに大切な基本となってくれます。
また、余りについての理論を理解すると、部屋割り論法を使った整数問題の理解にも役立ちます。
他に、n乗の差という記事では、高校や大学の整数で使う式の書き換えについて解説をしています。
それでは、これで今回のブログ記事を終了します。
読んで頂き、ありがとうございました。