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)
