方程式 \(ax+by=1\) が整数解をもつ\(a,b\)の条件はどのような条件でしょうか。
・\(ax+by=1\) の整数解に関する定理
方程式 \(ax+by=1\) について、次の定理が成り立ちます。
(定理)
\(a,b\)を自然数とする。
\(am+bn=1\) を満たす整数\(m,n\)が存在する
\(\leftrightarrow\)
\(a,b\)は互いに素である。
\(a,b\)を自然数とする。
\(am+bn=1\) を満たす整数\(m,n\)が存在する
\(\leftrightarrow\)
\(a,b\)は互いに素である。
つまり、方程式を満たす整数解が存在するならば、\(a,b\)は互いに素で、
また、\(a,b\)が互いに素ならば、方程式が整数解をもつということです。
「互いに素」ということがポイントになります。
また、\(a,b\)が互いに素ならば、方程式が整数解をもつということです。
「互いに素」ということがポイントになります。
なお、\(a,b\)を\(0\)でない整数としても、上記定理は成り立ちます。
例えば\(a<0\) \(b>0\)の場合、
\((-a)(-m)+bn=1\) とすれば上記定理が適用でき、整数解については\(-m→m\)(例えば\(-m=3\) という解をもつとき、\(m=-3\) という解をもつことになる),互い素であることについては\(-a→a\)としても変わらないので、負の数の場合でも定理が成り立ちます。
例えば\(a<0\) \(b>0\)の場合、
\((-a)(-m)+bn=1\) とすれば上記定理が適用でき、整数解については\(-m→m\)(例えば\(-m=3\) という解をもつとき、\(m=-3\) という解をもつことになる),互い素であることについては\(-a→a\)としても変わらないので、負の数の場合でも定理が成り立ちます。
(定理の証明)
まず簡単な、
まず簡単な、
\(am+bn=1\)・・・① を満たす整数\(m,n\)が存在する
\(\rightarrow\)
\(a,b\)は互いに素である。
\(\rightarrow\)
\(a,b\)は互いに素である。
を証明します。
(証明(1))
\(a,b\)の最大公約数を\(g\)とすると、
\(a=ga’\), \(b=gb’\) (\(a’,b’\)は互いに素である整数) と表すことができる。
①に代入して
\(g(a’m+b’n)=1\)
\(a,b\)の最大公約数を\(g\)とすると、
\(a=ga’\), \(b=gb’\) (\(a’,b’\)は互いに素である整数) と表すことができる。
①に代入して
\(g(a’m+b’n)=1\)
\(g>0\) で\(g\)は\(1\)の約数だから \(g=1\)
よって、\(a,b\)は互いに素である。
次にこの逆である
\(a,b\)は互いに素である。
\(\rightarrow\)
\(am+bn=1\)・・・① を満たす整数\(m,n\)が存在する
\(\rightarrow\)
\(am+bn=1\)・・・① を満たす整数\(m,n\)が存在する
を証明しますが、その前に準備をします。
・準備① 部屋割り論法(鳩の巣原理)
部屋割り論法はそんなに難しいものでありません。人によっては当たり前と感じる方もいる人もいると思います。
(ア)\(n\)個の部屋に\(n+1\)人が入るとき、2人以上入る部屋が少なくとも1つ存在する。
(イ)\(n\)個の部屋に\(n\)人が入るとき、相部屋が無ければ、どの部屋にも1人ずつ人が入っている。
(ア)については、\(n=5\)として考えると
\(5\)個の部屋に\(6\)人が入るとき、どう入れても2人以上入る部屋ができるということです。5人までは1人ずつ入れることができますが、最後の1人がいるために相部屋ができてしまいます。
\(5\)個の部屋に\(6\)人が入るとき、どう入れても2人以上入る部屋ができるということです。5人までは1人ずつ入れることができますが、最後の1人がいるために相部屋ができてしまいます。
(イ)については、\(n=5\)として考えると
\(5\)個の部屋に\(5\)人が相部屋無しで入るとき、それぞれの部屋に1人ずつ人が入るということです。
\(5\)個の部屋に\(5\)人が相部屋無しで入るとき、それぞれの部屋に1人ずつ人が入るということです。
・準備② 定理(i)の証明
定理(i)
\(a,b\)を互いに素である自然数とする。
\(k\)を整数とするとき、\(ak\)を\(b\)で割った余りを\(r(k)\)と表す。
\(k,l\)を\(b-1\)以下の異なる自然数とするとき、\(r(k)≠r(l)\)である。
\(a,b\)を互いに素である自然数とする。
\(k\)を整数とするとき、\(ak\)を\(b\)で割った余りを\(r(k)\)と表す。
\(k,l\)を\(b-1\)以下の異なる自然数とするとき、\(r(k)≠r(l)\)である。
定理(i)を言い換えると、\(a・1,a・2,a・3,\)\(・・・a(b-1)\)をそれぞれ\(b\)で割った余りは全部異なるということです。
(定理(i)の証明)
「\(r(k)=r(l)\)」と仮定して背理法で示す。
「\(r(k)=r(l)\)」と仮定して背理法で示す。
仮定より
\(ak-al=bM\) (\(M\)は整数)
\(ak-al=bM\) (\(M\)は整数)
よって
\(a(k-l)=bM\)
\(a(k-l)=bM\)
\(a,b\)は互いに素であるので、
\(k-l\)は\(b\)の倍数。
\(k-l\)は\(b\)の倍数。
しかし、\(0<k<b\), \(0<l<b\) より
\(-b<k-l<b\) だから
\(k-l=0\) つまり \(k=l\)
これは\(k,l\)が異なる自然数であることに矛盾。
よって、\(r(k)≠r(l)\)である。
\(-b<k-l<b\) だから
\(k-l=0\) つまり \(k=l\)
これは\(k,l\)が異なる自然数であることに矛盾。
よって、\(r(k)≠r(l)\)である。
準備が終わったので、それでは本題の証明です。
\(a,b\)は互いに素である。
\(\rightarrow\)
\(am+bn=1\)・・・① を満たす整数\(m,n\)が存在する
\(\rightarrow\)
\(am+bn=1\)・・・① を満たす整数\(m,n\)が存在する
(証明(2))
定理(i)より、
\(r(1),r(2),・・・,r(b-1)\)はどの2つも異なる。
また
\(a,b\)が互い素であるから、\(a・1,a・2,a・3,\)\(・・・a(b-1)\)は\(b\)の倍数ではない。よって
\(r(1),r(2),・・・,r(b-1)\)はどの2つも異なる。
また
\(a,b\)が互い素であるから、\(a・1,a・2,a・3,\)\(・・・a(b-1)\)は\(b\)の倍数ではない。よって
\(1≦r(1),r(2),・・・,r(b-1)≦b-1\)
したがって、部屋割り論法(イ)より
\(r(1),r(2),・・・,r(b-1)\)は、それぞれ別々で、\(1,2,3,・・・,b-1\)のいずれかである。
ゆえに、\(r(1),r(2),・・・,r(b-1)\)の中に\(1\)となるものが存在し、それを\(r(s)\)(\(1≦s≦b-1\))とする。
\(r(1),r(2),・・・,r(b-1)\)は、それぞれ別々で、\(1,2,3,・・・,b-1\)のいずれかである。
ゆえに、\(r(1),r(2),・・・,r(b-1)\)の中に\(1\)となるものが存在し、それを\(r(s)\)(\(1≦s≦b-1\))とする。
\(r(s)\)は、\(as\)を\(b\)で割った余りだから商を整数\(q\)とすると
\(as=bq+1\)
\(as+b(-q)=1\) となるので
\(m=s\) , \(n=-q\) とすれば、\(m,n\)は整数なので
\(am+bn=1\) を満たす整数\(m,n\)が存在する。
\(as=bq+1\)
\(as+b(-q)=1\) となるので
\(m=s\) , \(n=-q\) とすれば、\(m,n\)は整数なので
\(am+bn=1\) を満たす整数\(m,n\)が存在する。
以上になります。お疲れ様でした。
ここまで見て頂きありがとうございました。