２つの自然数の最大公約数は、ユークリッドの互除法で機械的に求めることができる。
ここでは、その基礎となる整数の性質を示す。
【性質１】
自然数a, b (a>b)において、a を b で割った商を q 、余りを r とすると、
a = b q + r ･‥ ①
このとき、自然数 aとb は互いに素ならば、b とr も互いに素である。
【証明】
背理法で証明する。b と r が互いに素でないと仮定する。
このとき、b と r の最大公約数 g ( g > 1) が存在し、
b = b’ g , r = r’ g (b’, r’ は互いに素) と表せる。これを①に代入すると、
a = b’ q g + r’ g = (b’ q + r’)g となり、 g はaとb の公約数となるから、「aとb は互いに素」に矛盾する。
したがって、 aとb が互いに素ならば、b とr も互いに素である。
【性質２】
自然数a, b (a>b)において、a を b で割った商を q 、余りを r とすると、
a = b q + r ･‥ ①
このとき、自然数 aとb の最大公約数が g ならば、b とr の最大公約数も g である。
【証明】
a と b の最大公約数を g とすると、a, b は次式で表せる。
a = a’ g , b = b’ g (a’とb’は互いに素) ･‥ ②
a’ を b’ で割った商を q’、余りを r’とすると
a’ = b’ q’ + r’ ( a’ > b’ > r’ , b’ と r’は互いに素) ･‥ ③
③の両辺を g 倍すると
a’ g = b’ g q’ + r’ g
a = b q’ + r’ g ･‥④
b’ > r’ より、b = b’ g > r’ g であるから
a を b で割った商は q’、余りは r’ g である。
①, ④より、q = q’ , r = r’ g ･‥⑤
②,③,⑤より、b = b’ g , r = r’ g であり、b’ と r’ は互いに素であるから g は b と r の最大公約数である。証明終り。
問１
1207と994の最大公約数を求めよ。
[解法1]
1207＝994＋213
ここで、213を素因数分解すると
213＝3・71
1207,994は共に3の倍数ではないから、最大公約数は71か1である。
1207,994を71で割ると
1207＝71・17
994＝71・14
17と14は互いに素であるから、求める解は 71 である。
[解法２]
ユークリッドの互除法より、
1207＝994＋213
994＝213・4＋142
213＝142＋71
142＝71・2
以上より、求める解は 71 である。
問2
5n+1と6n+4の最大公約数が7になるような100以下の自然数nをすべて求めよ。
解答
6n＋4=(5n＋1)・1＋n＋3
5n＋1=(n＋3)・5－14
であるから、n＋3は7の倍数であるが、2の倍数でない。
また、4 ≦ n＋3 ≦ 103であるから n＋3＝7, 21, 35, 49, 73, 77, 91
よって、 n＝4, 18, 32, 46, 60, 74, 88
コメントをお書きください