Question

梨花

ユークリッドの互除法を使います。
(2)です。
なせaの最大公約数と最大公約数は一緒なのでしょうか？？？ちょっと書き込んでみたんですがよくわからないです💧

あとなぜn+3は2の倍数ではないのでしょうか？

解説お願いします！！🙇‍♀️💦💦

54 ユークリッドの互除法
(1)95)と254) の最大公約数を求めよ.数が大きすぎますね
(2) 2つの整数2n+30と+3の最大公約数が3となるような30以下の
自然数n をすべて求めよ.
解答〕
(1957 を 754 で割ると商が1で余りが 203 になる.次に, 754を203で割る.これ
を続けると、
957-7541+203
754-203・3+145
203=145・1 + 58
145=58・2+29
58=29・2+0
よって, aとbの最大公約数をged (a, b) と表すと,
gcd(957,754)=gcd(754,203) = gcd(203,145)= gcd(145,58)=gcd(58,29)=29
が成り立つから,957 と 754 の最大公約数は 58 と29の最大公約数と等しく, 29
これらの計算は、次のような筆算を使うと便利である
2 2 1 3 1
29) 58 145 203) 754) 957
145 609 754
58 116
0 29 58 145 203
(2) 2n+30 を n +3で割ると,商が2で余りが 24 となる. つまり,
2n+30=(n+3) ・2+24
が成り立っていて, ユークリッドの互除法より,
gcd(2n+30,n+3)= gcd(n+3,24)
である. よって, 条件から,
文系
数学の必勝ポイント
gcd(n+3,24)=3
であるが,24=233 に注意すると, ① が成り立つ条件は,
+3が3の倍数であり,かつ, 2の倍数でないこと
である. 1≦n≦30より, 4≦n+3≦33であるから, ② を満たす整数 n +3は,
n+3=9, 15, 21,27,33
n=6,12,18,24,30
解説講義
2つの正の整数a,b (a>b) に対して, a を6で割った余りを (0) とする. このとき,
( α ともの最大公約数) = (bとrの最大公約数)
となる.このことを繰り返し用いることによって最大公約数を求めることをユークリッドの
互除法という.
最大公約数の求め方 (a>b>0とする)
・割と周の最大公約数
=宮園と金の最大数
αを6で割った余りをr(>0) とすると,
割れる数に割る数の十
1
(αとbの最大公約数) = (bとrの最大公約数)
7
良い
73

Answer 1

✨ ベストアンサー ✨

すけ

イメージはこんな感じです。

もし、n+3が3の倍数かつ2の倍数だったら、
n+3と24の最大公約数は6以上になります。

梨花

あ！理解です！ありがとうございます！