Question

hachi

青チャートIAの数学Aの例題126（1）がわかりません

丁寧な解説待ってます🙇

504
基本例題 126 互除法の応用問題
(1) 2つの整数m,nの最大公約数と3m+4n, 2m+3n の最大公約数は一致す
ることを示せ。
(2) 7n+4と8n+5が互いに素になるような100 以下の自然数nは全部でいく
つあるか。
わからん
指針 最大公約数が関係した問題では, p.501 基本事項 ①
(*)で示した,右の定理を利用して,数を小さくし
ていくと考えやすい。
解答
2 数A, B の最大公約数を (A, B) で表す。
(1) 3m +4n=(2m+3n) 1+m+n,
2m+3n-(m+n)·2+n,
本問のように,整式が出てくるときは,まず, 2つの
式の関係を α=bg+r の形に表す。
次に,式の係数や次数を下げる要領で変形していくとよい。
m+n=n·1+m
MUT
よって
(3m+4n, 2m+3n)=(2m+3n, m+n)
=(m+n, n)=(n, m)
したがって,m,nの最大公約数と3m +4n, 2m+3n の最
大公約数は一致する。
[3m+4n=a
なん
a=batr 等しい
|m=3a-4b
p.501 基本事項 ①
Takin
aとbの最大公約数
不
| bとrの最大公約数
2+²+1-885=ESE
差をとって考えてもよい。
3m+4n-(2m+3n)=m+n
2m+3n-(m+n)=m+2n
m+2n-(m+n)=n
m+n-n=m
EPO
(S)

青チャートia 数学a 整数の性質

Answer 1

✨ 最佳解答 ✨

exod

最大公約数の定理より、
a=bq+rにおいて、
最大公約数をgcd(x,y)のように表記すると、
gcd(a,b)=gcd(b,r)がなり成り立ちます。

上の定理を使うと、

3m+4n=(2m+3n)･1+m+n
→gcd(3m+4n,2m+3n)=gcd(2m+3n,m+n)･･･①

2m+3n=(m+n)･2+n
→gcd(2m+3n,m+n)=gcd(m+n,n)･･･②

m+n=n･1+m
→gcd(m+n,n)=gcd(n,m)･･･③

①、②、③を繋げると

gcd(3m+4n,2m+3n)= gcd(n,m)

となり、3m+4nと2m+3nの最大公約数と、mとnの最大公約数が同じだと分かります。

(定理の証明)

a=bq+r･･･④

r=a-bq･･･⑤

aとbの最大公約数をm、bとrの最大公約数をnとします
。

gcd(a,b)=m
gcd(b,r)=n

公約数をcd(x,y)と表記すると、

⑤より、cd(b,r)=m
(mはrの約数)
bとrの最大公約数はnなので、
m≦n

cd(a,b)=n
(nはaの約数)
aとbの最大公約数はmなので、
n≦m

よって、m=n
つまり、
gcd(a,b)= gcd(b,r)

です。