少し難しい整数不定方程式－合同式の利用－

こんにちは。東久留米市の学習塾塾長です。

台風が過ぎて吹き返しの風が強いですが、良い天気になりました。これで台風もお仕舞いだといいですね。

近頃、東大大学院入試に出題された、中学生にも解ける簡単な問題を取り上げてきたので、今回は難しい問題です。一昨日紹介した合同式を使うので、それに馴染んでいただくと良いかと思います。

出典は、Ｔｅｒｅｎｃｅ　Ｔａｏ，“ｓｏｌｖｉｎｇ　ｍａｔｈｅｍａｔｉｃａｌ　ｐｒｏｂｌｅｍｓ”　で、問題は、
「ｎとｘが整数のとき、
２^n＋７＝ｘ＾2
の解をすべて求めよ。」
というものです。（ここで、２^n は２のｎ乗、ｘ^2 はｘの２乗を表します）

問題文も短く、覚えやすくて良いですね。与式は、ｎとｘが整数なので、ディオファントス方程式と呼ばれる整数の不定方程式です。さらに、右辺が正の整数ですから、ｎ＞０となります。

一見、ｎ＝１でｘ＝±３、また、左辺の７がなければ、ｎが偶数（ｎ＝２ｍ、ｍは正の整数）のとき、ｘ＝±２^m　が解になるのは判るのですが、どこから切り込んでいくか難しいところです。

以前に整数の不定方程式の基本解法テクニックは、
・因数分解を使う
・大小関係を使う
・剰余で分類する
を挙げましたが、Ｔａｏ教授は、モジュラー算術（合同式⇔剰余で分類）と因数分解を挙げています。

結論としては、モジュラー算術を使って解くことになるのですが、与式をみると７が素数なので因数分解が魅力的に見えます。

そこで、与式
２^n＋７＝ｘ＾2　　（１）
の左辺の２^n　を移項して、右辺を因数分解してみます。すると、
７＝ｘ^2－２^n
＝（ｘ－２^m）（ｘ＋２^m）　（ｎ＝２ｍ）
となり、ｘ－２^m、ｘ＋２^m　が７の因数なので、それぞれ、－７、－１または１、７になります。

そこで、
ｘ－２^m＝－７
ｘ＋２^m＝－１
から、ｘ＝－４、２^m＝３
ｘ－２^m＝１
ｘ＋２^m＝７
から、ｘ＝４、２^m＝３
となり、ｎが偶数の場合、解はないことになります。（残念ながら得られた成果はこれだけです）

それでは次に、Ｔａｏ教授の挙げたもう一つのテクニックであるモジュラー算術を使うことにします。

それでは、モジュラー算術の法を２として２^n　の項を消去しましょう。まず、ｎ＝０のとき、（１）は、
１＋７＝ｘ^2
８＝ｘ^2
となり、これを満たす整数ｘはありません。

そこで、ｎ≧１の場合を考えると、
７≡ｘ^2（ｍｏｄ２）
１≡ｘ^2（ｍｏｄ２）
となります。

これは、平方数を２で割った余りが１となるということで、ｘが奇数のとき成立してしまい何の制限にもなっていません。

ここでＴａｏ教授は、“Ｔｏ　ｒｅｓｔｒｉｃｔ　ｔｈｅ　ｖａｌｕｅ　ｏｆ　ｘ^2，ｗｅ　ｈａｖｅ　ｔｏ　ｃｈｏｏｓｅ　ａ　ｄｉｆｆｅｒｅｎｔ　ｍｏｄｕｌｕｓ．Ｗｉｔｈ　ｔｈｉｓ　ｌｉｎｅ　ｏｆ　ｔｈｏｕｇｈｔ・・・”（ｘ^2の値を制限するために、別の法を選ばなくてはならない。この考え方に沿って・・・）と法を２から４に変更します。（この辺りが凄いですね）

つまり、
２^n＋７＝ｘ^2（ｍｏｄ４）
を調べるのですが、これをｎで場合分けすると、

ｎ≧２のとき、
０＋７≡ｘ^2（ｍｏｄ４）
３≡ｘ^2（ｍｏｄ４）　　（２）

ｎ＝１のとき、
２＋７≡ｘ^2（ｍｏｄ４）
１≡ｘ^2（ｍｏｄ４）　　（３）

ｎ＝０のとき、
１＋７≡ｘ^2（ｍｏｄ４）
０≡ｘ^2（ｍｏｄ４）
となります。

一方、ｘ＝４ｐ＋ｑ　（ｐは整数、ｑ＝０、１、２、３）とすると、
ｘ^2＝（４ｐ＋ｑ）^2
＝１６ｐ^2＋８ｐｑ＋ｑ^2
なので、
ｘ^2≡ｑ^2（ｍｏｄ４）
　　≡０、１（ｍｏｄ４）
となり、（２）はあり得ないことになります。（上手く行きました）つまり、ｎ＝１または０となり、それぞれの場合を調べると、

ｎ＝１の場合、（１）から
２＋７＝ｘ^2
９＝ｘ^2
ゆえに、
ｘ＝±３

ｎ＝０の場合、前述したように、
ｘ＝±２√２
となり、これはｘが整数の条件に反します。

したがって、正解は、ｎ＝１、ｘ＝±３となります。

それにしても上手くｘ^2を制限できたものです。一連のテクニックを頭に入れておくと良いかもしれません。