基本例話 134 互除法の応用問題
(1)
000
nの最大公約数と3m+4n, 2m+3n の最大公約数は一致
することを示せ。
p.553 基本事項
(2) 7 +48 +5が互いに素になるような100 以下の自然数nは全部でいく
つあるか。
指針 最大公約数が関係した問題では, p.553 基本事
項(*)で示した、 右の定理を利用して, 数
を小さくしていくと考えやすい。
本問のように、多項式が出てくるときは,まず,
2つの式の関係をα = bg+r の形に表す。
次に, 式の係数や次数を下げる要領で変形して
いくとよい。
880
80
2 数A, B の最大公約数を (A,B) で表す。
解答 (1) 3m+4n=(2m+3n) 1+m+n,
2m+3n=(m+n) ・2+n,方で割
m+n=n·1+m
よって
(3m+4n, 2m+3n)=(2m+3n, m+n)
=(m+n, n)=(n, m)
are Carr
したがって,m,nの最大公約数と3m+4n, 2m+3n
の最大公約数は一致する。
se
aとbの最大公約数
a=batr
等しい
bとrの最大公約数
284, 1-8ES ESE
2048:29-
差をとって考えてもよい。
3m+4n-(2m+3n)=m+n
2m+3n-(m+n)=m+2n
2 m+2n-(m+n)=n
m+n-n=m