SOOO00
504
基本 例題126 互除法の応用問題
(1) 2つの整数 m, n の最大公約数と 3m+4n, 2m+3n の最大公約数は一。
ることを示せ。
(2) 7n+4 と 8n+5が互いに素になるような 100 以下の目然数nは全部でい。
つあるか。
p.501 基本事項]
laとbの最大公約数
指針> 最大公約数が関係した問題では, p.501 基本事項1
(*)で示した, 右の定理を利用して, 数を小さくし
ていくと考えやすい。
本間のように,整式が出てくるときは, まず, 2つの
式の関係を a=bq+rの形に表す。
次に,式の係数や次数を下げる要領で変形していくとよい。
a=bq+r
等しい
50
bとrの最大公約数
解答
2数A, Bの最大公約数を (A,B) で表す。
口(1) 3m+4n=(2m+3n)·1+m+n, o
2m+3n=(m+n)·2+n,
(差をとって考えてもよい。
3m+4n-(2m+3n)=m+n
2m+3n-(m+n)=m+2n
m+2n-(m+n)=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 の最
よって
m+n-n=m
e
大公約数は一致する。
