LoginSignup
0
0

More than 1 year has passed since last update.

「拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜」を参考にWolframAlphaでやってみた。

Posted at

オリジナル

distinct:明確(deepl翻訳より)

1-1. ユークリッドの互除法のやり方

Result
60
Prime factorizations
300 = 2^2×3×5^2 (5 prime factors, 3 distinct)
780 = 2^2×3×5×13 (5 prime factors, 4 distinct)

1-2. ユークリッドの互除法がなぜ必要か

Result
80
Prime factorizations
160 = 2^5×5 (6 prime factors, 2 distinct)
1200 = 2^4×3×5^2 (7 prime factors, 3 distinct)

計算ステップ回数が最悪になるケース

Result
1
Prime factorizations
89 is prime
144 = 2^4×3^2 (6 prime factors, 2 distinct)

3-2. 一次不定方程式 ax + by = c の整数解を求める具体例

Integer solution
x = 30 n + 12, y = -11 n - 4, n element Z

Result
x = -6 (5 n + 3) and y = 11 n + 7 and n element Z
Examples of integer solutions
y = 18 and x = -48
(つづく)

3-4. 拡張ユークリッドの互除法のアルゴリズム的記述

Integer solution
x = 10 n + 3, y = -37 n - 11, n element Z

Result
x = -10 n - 7 and y = 37 n + 26 and n element Z
Examples of integer solutions
y = 63 and x = -17
(つづく)

参考

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0