480
00000
基本例題112 互いに素に関する証明問題 (1)
(1) nは自然数とする。n+3は6の倍数であり,n+1は8の倍数であるとき,
n+9 は 24の倍数であることを証明せよ。
(2) 任意の自然数nに対して,連続する2つの自然数nとn+1は互いに素であ
ることを証明せよ。 ATUNATI p.476 基本事項 ② 基本 111
重要 114
CFS CITAT
指針 (1) 次のことを利用して証明する。 a, b, kは整数とするとき
a,bは互いに素で, ak が6の倍数であるならば,hは6の倍数である。
TRAXE SHES OU
MOC!
(2)
1
+1は互いに素⇔nとn+1の最大公約数は
nとn+1の最大公約数をg とすると
n=ga, n+1=gb (a,b は互いに素)
この2つの式からnを消去してg=1 を導き出す。 ポイントは
【CHART
A,Bが自然数のとき, AB=1 ならば A=B=1
求める。(間
解答
(1) n+3=6k,n+1=81 (k, lは自然数)と表される。
n+9=(n+3)+6=6k+6=6(+1)
n+9=(n+1)+8=81+8=8(1+1)+ M=5A
JES
RAJS
a,bは
11 ak = bl ならばんは6の倍数, 1はαの倍数
互いに素 ②2 aとbの最大公約数は 1
<<549°
よって
6(k+1)=8(+1) すなわち 3(k+1)=(2+1)
3と4は互いに素であるから,k+1は4の倍数である。このとき,l+1は3の倍数
したがって,k+1=4m (mは自然数) と表される。
である。 したがって,
ゆえに
n+9=6(k+1)=6.4m=24m
+1=3m と表されるから,
したがって, n +9 は 24の倍数である。
n+9=8.3m=24m
(2) nとn+1の最大公約数をg とすると
n=ga, n+1=gb (a,bは互いに素である自然数
と表される。 n = ga をn+1=gb に代入すると
ga+1=gb すなわち g ( 6-α) = 1
g,a,bは自然数で,n<n+1より6-a>0であるから g
g=1
(1)
としてもよい。
KBT BOE-S) IS =
よって, nとn+1の最大公約数は1であるから, nとn+1
(ST 8
は互いに素である。
)=(62.
注意 (2) の内容に関連した内容を,次ページの参考で扱っている。
BOSTOYEVS
nは自然数とする。 n +5は7の倍数であり、
Ad>D
An=ga, n+1=gb
積が1となる自然数は1だ
けである。
08
S
(()(A)
n+7は5の倍数であるとき、
