potisanのプログラミングメモ

プログラミング素人です。昔の自分を育ててくれたネット情報に少しでも貢献できるよう、情報を貯めていこうと思っています。Windows環境のC++やC#がメインです。

数学 実数直線の一般の整数解を求める場合に適当な整数解を探す理由

実数直線の一般の整数解を求めるとき、与式の適当な整数解を見つけて与式に代入して、それを与式から引いた式を作って答えを求めます。ふと適当な整数解ではなくて好き勝手な整数解を代入した式を引いてはいけない理由が分からなくなりました。

例えば「x, yが実数のとき、2x+3y=5の任意の整数解を任意の整数tで表せ」のような問題は次の手順で解けます。

  1. 適当な整数解を見つける。ここでは(x, y)=(1, 1)を見つけた。
  2. 与式に適当な整数解を代入した式を作る。ここでは2\cdot1+3\cdot1=5
  3. 与式から適当な整数解を代入した式を引く。ここでは(2x-2\cdot1)+(3y-3\cdot1)=5-5 \Leftrightarrow 2(x-1)=3(1-y)
    • 適当な整数解を探すのは互いに素な整数に分解済みの定数項5=2+3を得られるから。係数で括られていない定数項を消せれば総当たりでも同じ。
  4. 得られた式と互いに素な整数の性質から、任意の整数tを用いてx-1=3t\ (\Leftrightarrow x=3t+1)
  5. 前の式に代入して2\cdot3t=3(1-y) \Leftrightarrow 2t=1-y \Leftrightarrow y=1-2t
  6. 以上から、2x+3y=5の整数解は(x,y)=(3t+1, -2t+1)\ (tは任意の整数)

上の3で好き勝手な整数解を代入できるなら、1\cdot1+9\cdot1=51\cdot1+9\cdot1=3でも良いはずです。

そして気付きました。1\cdot1+9\cdot1=51\cdot1+9\cdot1=3も等号が成り立たないので偽の命題で、真の命題を積み上げる推論の途中では使えません。1\cdot1+9\cdot1\neq51\cdot1+9\cdot1\neq3なら真の命題ですが、今度は等式と不等式の引き算は定義されているかも分かりません。

適当な整数解でなければそもそも等式が成り立たない。落ち着いて考えれば当たり前の理由でしたが、迷っているときは意外と当たり前を忘れているものでした。

蛇足です。(論理体系にも拠ると思いますが)推論で偽の命題を用いてはいけないという教育を受けていない気がします。

関連情報