480
00000
基本 例題112 互いに素に関する証明問題 (1)
(1) nは自然数とする。 n+3は6の倍数であり,n+1は8の倍数であるとき、
n+9 は 24の倍数であることを証明せよ。
(2) 任意の自然数nに対して, 連続する2つの自然数nとn+1は互いに素であ
重要 114」
ることを証明せよ。
指針 (1) 次のことを利用して証明する。 α, b, kは整数とするとき
p.476 基本事項 ②. 基本 111
a,bは互いに素で, akbの倍数であるならば, kは6の倍数である。
(2)
+1は互いに素⇔nとn+1の最大公約数は 1
nとn+1の最大公約数をgとすると
n=ga, n+1=gb (a,bは互いに素)
この2つの式からnを消去してg=1 を導き出す。 ポイントは
A,Bが自然数のとき, AB=1 ならば A=B=1
[CHART
CAUCA
a,bは
①1 ak=blならばんは6の倍数,はαの倍数
互いに素 ②2 aとbの最大公約数は 1
解答
(1) n+3=6k, n+1=81(k, lは自然数) と表される。
n+9=(n+3)+6=6k+6=6(k+1)
n+9=(n+1)+8=8l+8=8(+1)
よって
6(k+1)=8(+1) すなわち 3(k+1)=4(+1)
! 3と4は互いに素であるから, k+1は4の倍数である。
したがって, k+1=4m (mは自然数) と表される。
ゆえに n+9=6(k+1)=6.4m=24m
したがって, n +9は24の倍数である。
(2)
とすると
n+1の最大公約数をg
n=ga, n+1=gb (a,bは互いに素である自然数)
と表される。 n=ga を n +1=gbに代入すると
ga+1=gb すなわち g (b-α)=1小
g, a,b は自然数で, n <n+1 より 6-α>0であるから
g=1
よって, nとn+1の最大公約数は1であるから, nとn+1
は互いに素である。
注意 (2) の内容に関連した内容を, 次ページの参考で扱っている。
練習
②112 +12を35で割った余りを求めよ。
1+1は3の倍数
このとき,
(2)を自然数とするとき 2n-1と2は
である。 したがって,
l+1=3m と表されるから、
n+9=8.3m=24m
としてもよい。
(1) nは自然数とする。 n +5 は 7の倍数であり, n +7は5の倍数であるとき,
◄n=ga, n+1=gb
積が1となる自然数は1だ
けである。
基
指針
C
L
a-
と
(2
a
こ
t
0
C
