A 回答 (4件)
- 最新から表示
- 回答順に表示
No.4
- 回答日時:
ユークリッドの互除法を使って一次不定方程式を解く手順は、
多くの本やサイトで解説されています。
「拡張互除法」と呼ばれていることが少なくないので、
こちらの名前で検索すると見つけやすいかもしれません。
「拡張」と呼ばれるのは、たぶん、どこかのコンピュータの
ライブラリの関数名の名残りです。
数学的には、拡張でもなんでもない、ユークリッドの互除法
そのものなんですけどね。
この手法にピンと来ない人があるのは、
「余りを他の式へ代入する」という説明に抵抗があるから
ではないかと思います。変数ではなくて
定数に何かを代入するとは何事か?って話です。
例えば 15=255-60×4 と 60=315-255×1 とから
15=255-(315-255×1)×4 という式を作ることを言ってるのですが、
「定数へ代入する」ことに違和感があるなら、
15=255-60×4 式中の 60 を 315-255×1 で置き換える
とでも言い換えておけばよいのではないでしょうか。
No.3
- 回答日時:
255 と 315 の約数では、先ず 両方共 5 の倍数であることは分かりますね。
で、それぞれを 5 で割って 57 と 63 になります。
これも 見ただけで 3 の倍数であることが分かります。
3 で割ると 17 と 63 になります。
17 は素数ですから これ以上の約数は ありません。
従って 255 と 315 の最大公約数は 5x3=15 で 15になります。
但し r と s を求める計算には 適していませんが。
ユークリッドの互除法を使えば、
(掛けるの記号を * で表します。)
315=255*1+60 → 60=315-255*1 ・・・①
255=60*4+15 → 15=255-60*4 ・・・②
60=15*4+0 。
(余りが 0 になったことで 最大公約数が 15 であることが分かる)
② に ① を代入する。
15=255-(315-255)*4=255*5-315*4=255*5+315*(-4) 。
つまり 15=255*5+315*(-4) 。
最大公約数=255r+315s から、最大公約数 15, r=5, s=-4 。
No.2
- 回答日時:
255と315の最大公約数を求めてみます。
315÷255=1あまり60…①
255÷60=4あまり15…②
60÷15=4あまり0…③
よって最大公約数は15
ここで、①~③の式のあまりに注目して各式を変形してみます。
①より、、、
60=315-255×1…④
②より、、、
15=255-60×4…⑤
⑤に④を代入して、、、
15=255-(315-255×1)×4
=255-(315-255)×4
=255-315×4+255×4
=255×5-315×4
=255×5+315×(-4)
つまり、
15=255×5+315×(-4)
よって、
15=255r+315×sを満たす(r,s)=(5,-4)
同様に288と639の最大公約数を求めてみます。
639÷288=2あまり63…①
288÷63=4あまり36…②
63÷36=1あまり27…③
36÷27=1あまり9…④
27÷9=3あまり0…⑤
よって最大公約数は9
①より、、、
63=639-288×2…⑥
②より、、、
36=288-63×4…⑦
③より、、、
27=63-36×1…⑧
④より、、、
9=36-27×1…⑨
ここから先は大変ですが、、、
⑨に⑧を代入して整理し、それに⑦を、さらに⑥を代入すれば、rとsが求まるはずです。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 大学受験 整数問題 Nを正の整数とする。 N+18がN+2の倍数となるようなNの値の個数を求めたい。 解説に、 1 2022/08/13 12:25
- 数学 写真は「ユークリッドの互除法」のイメージ図なのですが これで何故17が最大公約数になるのか分かりませ 2 2023/03/05 16:54
- 数学 再質問 写真は「ユークリッドの互除法」のイメージ図なのですが これで何故17が最大公約数になるのか分 4 2023/03/05 17:08
- C言語・C++・C# C#の問題で2つの整数a,bの最大公約数(GCD)を求めるユークリッドの互除法は,aをbで割った余り 2 2022/06/26 16:52
- 数学 ユークリッドの互除法、合同式の問題について 1 2022/05/08 11:49
- 計算機科学 高校1年の数学です! ユークリッドの互除法です。 写真の左上の問題で、問題集の答えは x=14、y= 1 2023/02/25 16:59
- 数学 最小公倍数と最大公約数の求め方で画像のような計算法があったのですが、理解できません。 なぜ2つ数24 4 2022/04/10 13:37
- 数学 中一数学の【最大公約数と最小公倍数】の問題です。 1問だけでも教えていただけると嬉しいです。 (1) 4 2022/08/01 10:19
- 数学 最小公倍数の求め方は分かるのですか、それ以降の公倍数の求め方が分からないため、教えていただきたいです 2 2022/05/25 13:28
- 数学 ユークリッドの互除法 添付についてですが、g(24337, 158)=g(158, 5)=1 という 2 2022/10/24 14:43
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
X2乗+Xの解き方について
-
(x+1)3乗と (x2乗+1)(x+1)(...
-
X二乗の解き方。
-
郡の問題です。
-
自明でない解を持つとき、行列...
-
2x^2+7x-3=0 の解き方を教えて...
-
(1+x)の5乗=1.20 の、解き...
-
隣接n項間漸化式の解き方
-
Lim〔x→∞〕(x^2-3x)はこういう...
-
場合の数
-
数学の魔法陣が解けません! 解...
-
1.805X -0.9025X^2=X^3 の解き...
-
どうやってとけばいいんですか...
-
3乗根
-
この解き方じゃダメですか? ま...
-
数学。 線形代数を始めたての者...
-
計数問題の解き方教えてください
-
鶴亀算ですが、解き方を教えて...
-
この問題を教えてください。な...
-
l x -2l≦3x を解く問題です。な...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
X2乗+Xの解き方について
-
(x+1)3乗と (x2乗+1)(x+1)(...
-
因数分解
-
写真の様な解き方はおかしいで...
-
因数分解のマイナスのくくり方...
-
この問題を教えてください。な...
-
逆三角関数 方程式
-
数学 因数分解の問題 abx ^2+...
-
逆三角関数の問題について
-
X二乗の解き方。
-
分数の分数乗
-
7で割れば5余り、5で割れば3余...
-
数学の魔法陣が解けません! 解...
-
郡の問題です。
-
(1+x)の5乗=1.20 の、解き...
-
√32の解き方を教えてください。...
-
√x log(x+2)の不定積分は部分積...
-
1+2+3・・・50 の解き方
-
Σ(k=1からnまで)(1/3)^kの解き...
-
0.0001m3 を (ml) の単位に変換
おすすめ情報