2数A, Bの最大公約数を(A, B) で表す。
(リ 7n+4 と 8n+5 が互いに素になるような 100以下の自然数nは全部でいく
次に、式の係数や次数を下げる要領で変形していくとよい。
最大公約数が関係した問題では,p.546 基本事項
互除法の応用問題
142
例題
2つの整数。
ることを示せ。
m. nの最大公約数と 3m+4n, 2m+3n の最大公約数は一致す
549
不
つあるか。
一例題141
aとbの最大公約数
いくと考えやすい。
a=bq+r
式の関係を a=bq+r の形に表す。
等しい
bとrの最大公約数
(1) 3m+4n=(2m+3n)·1+m+n.
2m+3n=(m+n)·2+n, t
m+n=n·1+m =-) 0-(1+)
(3m+4n, 2m+3n)= (2m+3n, m+n)
差をとって考えても
よい。
3m+4n-(2m+3n)
よって
=m+n,
+= (m+n, n)
2m+3n-(m+n)
=m+2n,
=(n, m)
m+2n-(m+n)=n.
したがって,m, nの最大公約数と 3m+4n, 2m+3n の最
大公約数は一致する。
m+n-n=m
3m+4n=a
m=3a-4b
別解
のとおくと
2
12m+3n=b
mとnの最大公約数をd.aとbの最大公約数をeとする。
0より,aとbはdで割り切れるから,dはaとbの公約数
である。ゆえに
同様に,2より,eはmとnの公約数で esd
3, ④から
したがって,最大公約数は一致する。
(2) 8n+5=(7n+4)·1+n+1, 7n+4=(n+1)·7-3
ゆえに
n=36-2a
m=dm', n==dn'
a=ea', b=eb' と
すると,①は
[d(3m'+4n')=a
d(2m'+3n')=b
2は
[e(3a'-4b')=m
le(36'-2a')=n
dse.
の
d=e
(87+5, 7n+4)= (7n+4, n+1)= (n+1, 3)
7n+4 と 8n+5は互いに素であるとき, n+1 と3も互いに a=bq-rのときも
素であるから,n+1 と3が互いに素であるようなnの個数
を求めればよい。 の見 の」 ま
2Sn+1<101 の範囲に, 3の倍数は 33個あるから, 求める
自然数は
(a, b)=(b, r)
が成り立つ。p.54€
の解説と同じ要領て
証明できる。
100-33=67 (個)
76
の新であるこ
ありがとうございます🙇♀️🙇♀️