504
00000
基本例題126 互除法の応用問題
(1) 2つの整数m,nの最大公約数と3m+4n, 2m+3n の最大公約数は一致す
ることを示せ。
(2) 7 +48 +5 が互いに素になるような 100 以下の自然数n
つあるか。
指針 最大公約数が関係した問題では, p.501 基本事項 ①
(*)で示した, 右の定理を利用して,数を小さくし
ていくと考えやすい。
本問のように,整式が出てくるときは,まず, 2つの
式の関係をa=bg+r の形に表す。
次に, 式の係数や次数を下げる要領で変形していくとよい。
解答
2 数A, B の最大公約数を (A,B) で表す。
口 (1) 3m+4n=(2m+3m) ・1+m+n,
2m+3n=(m+n) ・2+n,
m+n=n·1+m
よって
(3m+4n, 2m+3n)=(2m+3n, m+n)
=(m+n, n)=(n, m)
したがって,m,nの最大公約数と3m+4n,2m+3nの最
大公約数は一致する。
221 DE 01
① とおくと
2 は全部でいく
p.501 基本事項 ①
aとbの最大公約数
a=batr 等しい
3m+4n=a
m=3a-4b
[別解
2m+3n=b
n=36-2a
mとnの最大公約数をd, aとbの最大公約数をeとする。
① より αと6はdで割り切れるから, dはaとbの公約数
である。 ゆえに d≤e ......
e≦d
同様に,②よりはとnの公約数で
③ ④ から
d=e よって, 最大公約数は一致する。
(2) 8n+5=(7n+4)·1+n+1, 7n+4=(n+1).7-3
ゆえに
(8n+5, 7n+4)=(7n+4, n+1)=(n+1, 3)
7 +4と8+5は互いに素であるとき, n+1と3も互いに
素であるから, n +1と3が互いに素であるようなnの個数
を求めればよい。
R-X10
2≦n+1≦101 の範囲に,3の倍数は33個あるから 求める
自然数は
100-3367 (個)
練習
③ 126
(1)a,bが互いに素な自然数のとき,
3a+7b
2a+5b
とrの最大公約数
差をとって考えてもよい。
3m+4n-(2m+3n) = m+n
2m+3n-(m+n)=m+2n
m+2n-(m+n)=n
m+n-n=m
<m=dm',n=dn',
a=ed', b=eb' とする
① は
'd(3m'+4n')=a
d(2m'+3n')=b
re(3a'-4b')=m
e(36'-2a')=n
②は
a=bg-r のときも
(a, b)=(b, r)
が成り立つ。 .501の解説
と同じ要領で証明できる。
は既約分数であることを示せ。
(2) 3n+1と4n+3の最大公約数が5になるような50以下の自然数nは全部で
いくつあるか。
Op.514 EX87.88
以下
1
フ
r
角
例1
た
た
x
例2
方
a
VE
x
ア
G
C
Q
Ve
3
