整数の除法に関する例題について見ていきます。
(例題1)
\(n\)は整数で、\(0≦n<105\) とする。
\(n\)を\(3\)で割った余りを\(a\)
\(n\)を\(5\)で割った余りを\(b\)
\(n\)を\(7\)で割った余りを\(c\)
とするとき、\(n\)は
\(70a+21b+15c\)
を\(105\)で割った余りに等しいことを証明せよ。
除法の等式を利用して、\(a,b,c\)を\(n\)で表してみます。
(解答)
条件より
\(0≦a<3\), \(0≦b<5\), \(0≦c<7\) であり、
\(n=3k+a\), \(n=5l+b\), \(n=7m+c\) (\(k,l,m\)は整数)
と表すことができる。よって
\(a=n-3k\), \(b=n-5l\), \(c=n-7m\) であるから
条件より
\(0≦a<3\), \(0≦b<5\), \(0≦c<7\) であり、
\(n=3k+a\), \(n=5l+b\), \(n=7m+c\) (\(k,l,m\)は整数)
と表すことができる。よって
\(a=n-3k\), \(b=n-5l\), \(c=n-7m\) であるから
\(70a+21b+15c\)
\(=70(n-3k)+21(n-5l)+15(n-7m)\)
\(=106n-210k-105l-105m\)
\(=n+105n-210k-105l-105m\)
\(=105(n-2k-l-m)+n\)
\(n-2k-l-m\) は整数であり、\(0≦n<105\) だから
\(70a+21b+15c\) を\(105\)で割った余りは \(n\)である。
よって題意は示された。
(例題2)
\(13\)で割ると\(7\)余り、\(7\)で割ると\(2\)余る整数\(n\)がある。
この整数\(n\)を\(13×7\)で割るときの余りを求めよ。
例題1と同様に、\(n\)を2通りに表してみます。
(解答)
条件より
\(n=13k+7\)・・・①, \(n=7l+2\)・・・② (\(k,l\)は整数)
①②より
\(13k+7=7l+2\)・・・③
③は\(k,l\)の1次不定方程式なので、その解を求めても解けますが、今回は別の方法で解きたいと思います。
\(k,l\)が整数であることから、例えば \(l=・・・\) と表して、\(l\)が整数であることから\(k\)の条件を導きます。
\(k,l\)が整数であることから、例えば \(l=・・・\) と表して、\(l\)が整数であることから\(k\)の条件を導きます。
③より
\(l=\displaystyle\frac{13k+5}{7}\) (この式を帯分数の形にします)
\(=\displaystyle\frac{(14k-k)+5}{7}\)
\(=2k-\displaystyle\frac{k-5}{7}\)
\(l=\displaystyle\frac{13k+5}{7}\) (この式を帯分数の形にします)
\(=\displaystyle\frac{(14k-k)+5}{7}\)
\(=2k-\displaystyle\frac{k-5}{7}\)
\(l\)は整数なので、
\(k-5=7m\)・・・④ (\(m\)は整数) と表すことができる。
④\(k=7m+5\) を①に代入して
\(n=13(7m+5)+7\)
\(=13×7m+72\)
\(0≦72<13×7\) だから、求める余りは\(72\)
以上になります。お疲れさまでした。
ここまで見て頂きありがとうございました。