• 解決済み

    削除済みユーザー

    2023/11/21 21:41

    1 回答

    一次不定方程式の解を早く見つけられる方法がありましたら、教えていただけませんか？

    一つずつ書き出して代入するとすごく時間がかかってしまって…。

    1. 高校生
    2. 数学
    1. 高校生
    2. 数学
    3. 数学Ⅰ・A

    ベストアンサー

    ベストアンサー

    削除済みユーザー

    2023/11/21 23:57

    学校でだされる問題なら，最小解の絶対値が ≦5\leqq 5 くらいになるよう作られていると思われるので，虱潰しに代入していくのが一番速いと思います。


    方程式の係数が大きいなら，ユークリッドの互除法によって，22 つの係数のうち大きな方を小さな方で割った余りに置き換えていくと速く解けます（そして，これより速い方法は恐らく知られていないと思います。）


    たとえば 36m+25n=736m + 25n = 7 を解く場合：

    ・36x1+25x0=136x_1 + 25x_0 = 1 を解けば，(m,n)=(7x1,7x0)(m,n) = (7x_1,7x_0) が解になるので，

    　36x1+25x0=136x_1 + 25x_0 = 1 を解くことに帰着。

    ・11x1+25(x1+x0)=111x_1 + 25(x_1 + x_0) = 1 と書き換え，x2=x1+x0x_2 = x_1 + x_0 とおけば，

    　25x2+11x1=125x_2 + 11x_1 = 1 を解くことに帰着。

    ・3x2+11(2x2+x1)=13x_2 + 11(2x_2 + x_1) = 1 と書き換え，x3=2x2+x1x_3 = 2x_2 + x_1 とおけば，

    　11x3+3x2=111x_3 + 3x_2 = 1 を解くことに帰着。

    ここまで係数を小さくすれば，解の 11 つ (x3,x2)=(−1,4)(x_3,x_2) = (-1,4) を見つけるのは容易。x3,x2x_3,x_2 の定義式から (x1,x0)=(−9,13)(x_1,x_0) = (-9,13) がしたがい，よって (m,n)=(−63,91)(m,n) = (-63,91) がしたがう。


    質問者からのお礼コメント

    質問者からのお礼コメント

    すごくわかりやすくて助かりました！　ありがとうございます😊　

    そのほかの回答（0件）

    関連する質問

    もっとみる