東大２次試験(2017): 問題４(その4)

問(3)まではものの５分から10分ほどで到達できたのだが、問(4)には苦戦した。最大公約数というのは物理ではあまり使わない...というのは言い訳になるので、この辺でやめておこう。

問 (4) an+1 と an の最大公約数を求めよ。

nが偶数でも奇数でも、隣り合う、「パリティ」の異なる2種類の数列要素の間の最大公約数を考えることになるので、考え方は同じになる。従って、nを偶数と仮定して議論を進める。（nが奇数の場合は、議論の中で「パリティ」の異なる成分に入れ替えるだけでよい。）

まず、問(3)の結果から、全てのnにおいて、数列の要素a_nは約数２を持つことがすぐに結論できる。それはkが偶数の場合の因数1+(-1)^k=2に由来する。この「２」はkにもnにも依存しない共通の因数であるから、任意のnに対して、a_n+1とa_nの最大公約数の第一候補に挙げられる。実際、n=1,2,3,4あたりまで具体例で計算してみると2が正解らしいことが推測されるし、実際の正解も２である。

気になるのは、特別なnの値、例えばn=n₁において、偶然n₁に依存するような形で公約数が現れはしないか？という疑問である。もしn₁が非常に大きな数、たとえばn₁=123456789とかだったとしたら、n=1,2,3,4あたりまで具体例で計算したら２でした、なんてのは無駄な話となる。

n=n₁でa_n1 とa_n1+1が公約数Lを偶然持ったとする。すると、(2)で得た漸化式a₁a_n = a_n+1 - a_n-1 によって、a_n1+2も公約数Lを持つことになる。つまり、偶然どこかで公約数が偶然変更されるようなことがあれば、それはその後の要素にも引き継がれることになる。つまりn>n₁に属する任意のnにおいて、a_n+1とa_nの間に、nに依存しない最大公約数2Lが存在することになる。果たして、こんなことがあるかどうか調べてみよう。

まずは２項展開で得た式を見直してみる。ただし、和の部分はkについて偶数だけをとる、とせずにk=2jと書いてj=0, 1, 2,...で和をとるように書き直す。すると

となる。和に関するjの上限値はガウス記号と呼ばれる[n/2]で与えられる。これはn/2を越えない最大の整数という意味を持つが、若干鬱陶しいので、n=2m+1（奇数）のときと、n=2m（偶数）のときとで場合分けする。双方の場合について[n/2]=mとなる。

和の部分を具体的に書き下してみる。まずは奇数の場合(n=2m+1)から。ガウス記号が効いて、二項展開の最後の項は省かれてしまうため、

 となる。各項をよくみると、μが共通因子となって取り出せることがわかる。したがって、nが奇数の場合は

 と因数分解できる。ただしn=2m+1として、

である。初項(最終項)は、μ(ν)のみの2m(m)次式がになっているので、互いに素の場合には（自明な）共通因子は存在しない。

次に、nが偶数の場合は和の部分は二項展開における最高次の項がμに関してもνに関しても取り込まれるので、μとνが互いに素の場合には、新たな（自明な）共通因子はない。したがって、

ただし、n=2mとして

である。

問題ではμ=2, ν=5であり、共に素数である。この場合はNmもMmもともに奇数であることは容易にわかる。（それぞれの最終項は奇数だが、それ以外項はは２の倍数になっているので。）また、２と５は当然互いに素なので、μとνの間に公約数はない。

NmもMmも奇数であるから、もしこれが因数分解できるとしたら、それは奇数同士の積となる。したがって、Nmがたまたま偶数となって、nが奇数の場合の因数2μ=4が公約数になることはない。つまり４が最大公倍数になることはない。最大公倍数は２あるいは２×奇数の形になる。

上で考察したように、 仮にあるn=n₁において、たまたま奇数の因数2L+1がNmとMmに発生したとする。しかし、この因数はn>n₁でも因数となり続けることも上で確認した。だとすると、NmやMmの中に、mに依存しない共通因数がn>n₁において延々と発生し続けることになるが、MmやNmはμとνの多項式であり（μとνは互いに素）、どの項もmに依存した数になっているので、この多項式がmに依存しない因数を含むことはありえない。