-
![]()
004
as 00000
基本例題 126 互除法の応用問題
(1) 2 つの整数 m, n の最大公約数と3m+4n, 2m+3n の最大公約数は一致す
ることを示せ。
(2)7+4と8+5が互いに素になるような 100 以下の自然数nは全部でいく
p.501 基本事項 ①)
つあるか。
aとbの最大公約数
指針 最大公約数が関係した問題では, p.501 基本事項 ①
(*)で示した、 右の定理を利用して,数を小さくし
ていくと考えやすい。
本問のように,整式が出てくるときは,まず, 2つの
式の関係をa=bg+r の形に表す。
次に, 式の係数や次数を下げる要領で変形していくとよい。
解答
2 数A, B の最大公約数を (A, B) で表す。
(1) 3m+4n=(2m+3n)·1+m+n,
2m+3n (m+n)•2+n,
m+n=n・1+m
a=bg+r
(3m+4n, 2m+3n)=(2m+3n, m+n)
=(m+n, n)=(n, m)
したがって,m,nの最大公約数と3m+4n, 2m +3n の最
大公約数は一致する。
よって
3m+4n=a
m=3a-4b
「別解
① とおくと
2m+3n=b
|n=36-2a
mとnの最大公約数をd, aとbの最大公約数をeとする。
① より α とは dで割り切れるから, dはaとbの公約数
d≦e
である。 ゆえに
e≦d
同様に, ② より,eはmとnの公約数で
③④ から
d=e
よって, 最大公約数は一致する。
(2) 8n+5=(7n+4)·1+n+1, 7n+4=(n+1) 7-3
ゆえに
7 +4と8+5は互いに素であるとき, n +1と3も互いに
素であるから, n +1と3が互いに素であるようなnの個数
を求めればよい。
2≦n+1≦101の範囲に,3の倍数は33個あるから求める
100-3367 (個)
自然数は
等しい
bと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
[e(3a²-4b')=m
le(36'-2a')=n
②は
正員を無視してOK
(8n+5, 7n+4)=(7n+4, n+1)=(n+1, (3)
しょり
a=bgr のときも
(a, b)=(b, r)
が成り立つ。 .501の解説
と同じ要領で証明できる。
ES
ESS
