2017年3月10日金曜日

ユークリッドの互除法で最大公約多項式を求める

(2つの多項式の最大公約多項式を求める問題)

 次数の大きい方の多項式 f を、次数の小さい方の多項式 g で割り算して余りの多項式h(多項式gより次数の小さい多項式)を求め、その余りの多項式hで次数の小さい方の多項式 g を割り算する。
こうして余りの多項式を求めることで、少しづつ式の次数を小さくしていき、最後に式が割り切れて余りが0になった場合に、
式を割り切ることができた余りの多項式(次数が一番小さい)が、最大公約多項式です。

 この手順で最大公約多項式を求める方法を、ユークリッドの互除法と呼びます。

【例題1】
以下の多項式 f と g の最大公約多項式を求めよ。

【解答】

 この場合は、多項式 f が、多項式 g で割り切れましたので、多項式 g が最大公約多項式です。
(解答おわり)

(補足1)
 多項式fと多項式gを足し合わせる計算をするのは、多項式f=0と多項式g=0の連立方程式の解を計算する処理と等価です。
すなわち:
f(x)=0,
g(x)=0,
の解は、共通因数の積の式の解です。
共通因数の積の式は最大公約多項式です。

(補足2)
 ユークリッドの互除法で、多項式を多項式で割り算していくと、最終的な余りが定数になります。
(1)その余り定数が0の場合は、その0を余りにするように、多項式を割り切った式が、最大公約多項式です。
(2)その余り定数が0で無い場合は、最大公約多項式は存在しない。あえて言えば、最大公約多項式は「定数」である。

【例題2】
以下の多項式 f と g の最大公約多項式を求めよ。

【解答】

多項式 f を、多項式 g で割り算して余りの式=2hを得ました。
次に、 多項式 g を、多項式 h で割り算します。

この場合は、多項式 g が、多項式 h で割り切れましたので、多項式 h が多項式 f と多項式 g の最大公約多項式です。
(解答おわり)

リンク:
高校数学の目次

5 件のコメント:

  1.  
    http://math.stackexchange.com/questions/1599984/what-is-known-about-rational-points-on-the-ideal-of-relations-syzygy-ideal
      
       {X-x^2-y^2,Y-x^4-y^4,Z-x*y*(x^2-y^2)}={0,0,0}
      
    のとき 「俺達 (X,Y,Z) カンケ-ない 事は ない!  ∃;」

        ====「  今 何時? 」 「 syzygy (シジジィ)!」====


    関係式を 求め S; f(X,Y,Z)=0 と する。

    (1)Sを求め て S∩Z^3 を 求めて下さい;


    (2)Dual S=S^★ を 求め S^★∩Z^3 を 求めて下さい;



    曲面 は 伊達に グラフ 化 するものでは ない;

    (3) S , S^★ の グラフをも 願います;


    https://www.youtube.com/watch?v=cBphkk34zAU

    返信削除
  2.      ↓ に 【解答&解説】が 在ります。読んでください;

    【問題2】

    n^2 + m*n - 2*m^2 - 7*n - 2*m + 25 = 0 を満たすを満たす正の整数m, nの組をすべて求めよ


    【解答&解説】

    まず、n2 + mn - 2m2 - 7n - 2m + 25 = 0 をnについて整理します。
    n2 + (m - 7)n - 2m2 - 2m + 25 = 0
    これをnについて解くと、n = {7 - m ± √(9m2 - 6m - 51)}/2 …①
    いま、nは正の整数なので、9m2 - 6m - 51 = A2 (Aは非負整数) と置けます。
    つまり、√の中身が平方数となればよいと考えます。

    つぎに、9m2 - 6m - 51 = A2 を積の形に式変形して候補を絞り込みます。
    このとき、奇遇についても注意して候補を減らしておくと、不要な計算を回避できます。
    (3m - 1)2 - 1 - 51 = A2
    (3m - 1)2 - A2 = 52
    (3m - 1 + A)(3m - 1 - A) = 52

    ここで、(3m - 1 + A) - (3m - 1 - A) = 2A(偶数) であることも考慮して候補を絞り込めば
    (3m - 1 + A, 3m - 1 - A) = (26, 2) ⇔ (m, A) = (5, 12)
    このとき、n = (7 - 5 ± 12)/2 = 1 ± 6 (∵①)  n∈正の整数 より、n = 7  ∴(m, n) = (5, 7)

    ------------------------------------------------------------------------------------------------

    簡単故 もっと 簡単に 叶うでしょう が ほんの 少し 改竄します;

           容易な↓をさっと解いて下さい;
           
    n^2 + m*n - 2*m^2 - 7*n - 2*m + 25 = 0 (<---改竄前)

    x^2 + x*y - 7*x -2*y^2 -2*y + 219 = 0 (<----改竄後)


    (1) x^2 + x*y - 7*x -2*y^2 -2*y + 219 = 0   は    双曲線で

    容易ですが この上の格子点を 全て  求め て 下さい;


    (2) この 双対曲線 も 双曲線であることの 証明は 容易ですが 直ぐ行い


    >私はあなたに重要なお願いがあります。

    >I have an important favor to ask.

    ● 双対曲線 上の 格子点を 全て 導出過程を 明記し 求めて下さい;

    (<-------- 此処が メイン です)


    返信削除
  3.       低次曲面 S; 15 x^2+10 x y+10 x z+5 y^2+5 z^2-1=0
       
       の 君の名は? 「対応する Japan の 人 が 愛する 行列を 求め,固有値 KARA」
       
        ________ だ。
       
       
        https://www.youtube.com/watch?v=Dbwv_uo33qc
       
       
       低次曲面 Sの 双対曲面 S^★ を 多様な発想で求めて下さい;
       
       
       獲た S^★  の 君の名は? 「対応する Japan の 人 が 愛する 行列を 求め,固有値 KARA」
       
        ________ だ。
       
       
        さて 流行りの 整数解の問題 を 解法を明記 し どうぞ! ;
       
       S∩Z^3=
       
       S^★∩Z^3=
       
       「 大 H i n t ;上の格子点の問題は 入試に出題可能 」 と 少女 A .
      
       https://www.youtube.com/watch?v=SDltYpt9mAk
      
      
       えっ? 「もっと Hint が 欲しい?」
      
          ご希望に添い だい Hint 「 S^★達は 箱入り 娘 」
      
       即ち S^★ なる 束縛条件のもとで z の 最小値 最大値 を求める 等で.
      
       
    >ラグランジュの未定乗数法(method of Lagrange multiplier)とは、束縛条件のもとで最適化を行うための数学(解析学)的な方法である。いくつかの変数に対して、いくつかの関数の値を固定するという束縛条件のもとで、別のある1つの関数の極値を求めるという問題を考える。各束縛条件に対して定数(未定乗数、Lagrange multiplier)を用意し、これらを係数とする線形結合を新しい関数(未定乗数も新たな変数とする)として考えることで、束縛問題を普通の極値問題として解くことができる方法である。
       
       
       
       

    返信削除
  4. http://www.cybernet.co.jp/maple/tech/math/mws_0016.html

    返信削除
    返信
    1. 多項式の拡張互除法のソフトウェアのサイトの紹介をありがとうございました。参考になります。

      削除