-
35. Go A
例題 19 ユークリッドの互除法の応用
思考プロセス
nは2桁の自然数とする。 2つの自然数 6m² + 14n +55 と2m² +4n+17
互いに素ではないとき,この2数の最大公約数を求めよ。 さらに、このよ
うなnをすべて求めよ。
« ReAction 素因数分解が容易でない2数の最大公約数は, ユークリッドの互除法を利用せよ
互除法の原理… 2つの自然数a, b に対して,a=bg+r (r≠0) のとき
(α ともの最大公約数)=(bとrの最大公約数)
6n2+14n+55=3(2n²+4n+17) + 2n+4
411
(6n2+14n+55と2n² +4n+17の最大公約数)= (2n²+4n+17 と の最大公
2次
2次
2次
1次
次数が下がる
次数を下げる
繰り返すと0次 (整数)になる
解 6m² +14n+55を2m²+4n+17で割ると
例題
9
IA
6m² +14n+55=3(2n²+4n+17)+2n+4
2n²+4n+17を2n+4で割ると
2m² +4n+17=n(2n+4)+17
A=BQ+R の形をつ
る。
301 よって, 6m² +14 +55 と 2n² +4n+17 の最大公約数は互除法の原理
2n+4と17の最大公約数と一致する。
ここで, 17 は素数であるから, 2n+4 と 17 の最大公約数
は1または17であるが, 6n² + 14n+55 と 2n² +4n+17 は
互いに素ではないから, 最大公約数は1ではない。
よって, 求める最大公約数は 17
ゆえに, 2n+4は17の倍数である。
ここで, nは2桁の自然数であるから
24≦2n+4 <204
(6m² +14n+55と
2n²+4n+17 の最大公
=(2n²+4n+17 と 2
の最大公約
=
(2n+4と17
の最大公約
また, 2n+4は偶数であるから
2n+4=34,68, 102, 136,170
したがって
n=15,32,49,66,83
Point...ユークリッドの互除法による多項式の最大公約数の求め方
2つの多項式 A, B の最大公約数を求める手順
①AをBで割ったときの余りR を求める。
(2) BをR で割ったときの余り R2 を求める。
(3) ②と同様の作業を R が整数となるまで繰り
返す。 その整数 R が求める最大公約数である。
候補を絞り込む
nが2桁の自然数 す
わち 10≦x<100 である
ことから, 2n+4の
得る値の範囲を絞り込む
2n+4=2(n+2) より
2n+4は偶数である。
6n2+14n+55=3(2m²+4n+17)+2n+4
2n²+4n+17=n(2n+4)+17
(0次(整数)
最大公約数は17 +3
習 19 n は 50 以上100以下の自然数とする
2つの白枠数 31
2
12m +76 [と