Fussy's Diary

「アルゴリズムのコーナー」にて新たなテーマとして「パターン認識」を追加しました。最初は「凝集型クラスタリング」を紹介しています。これが今年最後の更新になりそうです。

予定より内容がふくらんでしまい、だいぶ時間がかかってしまいましたが何とか今年中に公開することができました。次のお題もだいたいは決まっているものの、どこで区切りを付けるか少々悩んでいます。まあ、今度はのんびりと進めることにします。

「数学問題 bot ( 個人用 )」から京大の問題を選んでみました。例によって合っている保証はありません。

-----

(1) 2^1/3 が無理数であることを示せ。
(2) P(x) は有理数を係数とする x の多項式で、P(2^1/3) = 0 を満たしているとする。このとき P(x) は x³ - 2 で割り切れることを証明せよ ( 2012 京大 )

(1) 2^1/3 = a / b ( 但し、a, b は互いに素な整数で b ≠ 0 とする ) と仮定します。この等式が成り立てば 2^1/3 は有理数です。このとき、両辺を 3 乗して

2 = a³ / b³ より a³ = 2b³

となり、a は 2 を素因数に持つことになります。a = 2c とすると、

8c³ = 2b³ より b³ = 4c³

となり、b は 2 を素因数に持つことになるので a, b が互いに素であるという仮定に反します。したがって、2^1/3 は有理数ではなく、無理数であることが証明されました。

(2) P(2^1/3) = 0 より P(x) は因数 x - 2^1/3 を持ちます。そこで

P(x) = ( x - 2^1/3 )Q(x)
Q(x) = Σ_k{0→n-1}( a_kx^k )

とすると、

P(x)
= ( x - 2^1/3 )( a_n-1x^n-1 + a_n-2x^n-2 + ... + a₀ )
= a_n-1xⁿ + ( a_n-2 - 2^1/3a_n-1 )x^n-1 + ... + ( a₀ - 2^1/3a₁ )x - 2^1/3a₀

となります。P(x) の係数は有理数なので、Q を自然数全体の集合としたとき a_k-1 - 2^1/3a_k ∈ Q, a_n-1 ∈ Q, 2^1/3a₀ ∈ Q が成り立つ必要があります。しかし、2^1/3 は無理数なので、

(i) a_k = 0 ( 0 < k < n ) かつ 2^1/3a₀ ∈ Q

または

(ii) a_k-1 - 2^1/3a_k = 0 ( 0 < k < n ) かつ 2^1/3a₀ ∈ Q

が成り立つ必要があります。(i) の場合、P(x) = a₀x - 2^1/3a₀ となり、2^1/3a₀ ∈ Q ならば任意の q ∈ Q に対して a₀ = q / 2^1/3 で q = 0 以外では a₀ は無理数となるため条件を満たしません。q = 0 のとき P(x) = 0 なので、P(x) は x³ - 2 で割り切れることになります。

(ii) の場合、

a_k-1 = 2^1/3a_k より a_k = 2^-1/3a₀

なので、

P(x) = 2^-(n-1)/3a₀xⁿ - 2^1/3a₀

となり、2^1/3a₀ = q ∈ Q とすると a₀ = 2^-1/3q となります。このとき、

P(x) = 2^-n/3qxⁿ - q

なので、2^-n/3q が有理数であるためには n = 3k ( k は 0 以上の整数 ) でなければなりません。k = 0 のときは n = 0 なので

P(x) = qx⁰ - q = 0

で成り立ちます。k ≥ 1 のときは

P(x)
= 2^-kqx^3k - q
= 2^-kq( x^3k - 2^k )
= 2^-kq( x³ - 2 )( x^3(k-1) + 2x^3(k-2) + ... + 2^k-1 )

となるので、命題が成り立つことが証明されました。