-
![]()
X
Clear
串
分割21 (令和…..
480
なぜこれらは
表記を変えているのでか?
×
分割19 (第3...
解答
B
CHART
(1)
Clear
00000
基本例題 112 互いに素に関する証明問題 (1)
(4) nは自然数とする。 n+3は6の倍数であり, n+1は8の倍数であるとき､
n+9は24の倍数であることを証明せよ。
任意の自然数nに対して､連続する2つの自然数nとn+1は互いに素であ
の方の解
ることを証明せよ。 (21はおさてんどん
P.476 基本事項 (2) 基本111114
指針 (1)次のことを利用して証明する。a,b,kは整数とするとき
く
生物 白紙法
a,bは互いに素で, akがもの倍数であるならば、はの倍数である。
n=ga,n+1=gb(a,bは互いに素
(2)nn+1は互いに
とn+1の最大公約数は
nとn+1の最大公約数をとすると
この2つの式から消去して 9-1を導き出す｡ ポイントは
A.Bが自然数のとき, AB 1 ならば A=B=1
3-664 (k, は自然数)と表される。
n+9= (n+3)+6=6k+6=6(k+1)
n+9 (n+1)+8=81+8=8(7+1)
XO
よって
6(k+1)=8(Z+1) すなわち 3 (k+1)=4(+1)
3と4は互いに素であるから,k+1は4の倍数である。
したがって, k+1=4m (m は自然数) と表される。
ゆえに n+9=6(k+1)=6.4m24m
したがって n+9は24の倍数である。
(2)+1 最大公約数を」とすると
ngan+1=gb (a,bは互いに素である自然数)
と表される。 nga を n+1=gb に代入すると
ga+1=gb すなわち (b-g) =1
9, a,bは自然数で,n<n+1 より b-a>0であるから
g=1
よって, nとn+1の最大公約数は1であるから nとn+1
は互いに素である。
注意 (2)の内容に関連した内容を、 次ページの世で扱っている。
α b は 1 ak = bl ならば kの倍数の倍数
互いに素 [2] αとの最大公約数は1
としてもよい。
<n=ga, n+1=gb
積が1となる自然数はまだ
けである。
99
(1) nは自然数とする。 n+5は7の倍数でありn+7は5の倍数であるとき､
112
+1235で割った余りを求めよ。
(2) nを自然数とするとき, 2n-1と2n+1は互いに素であることを示せ。
[ 中央大 (2) 広島修道大) p.484 EN7
X 大森徹遺伝問題･･･
Ć D Đ tlas
CHART 互いに素であることの証明
X
基本例題13 互いに素に関する証明問題 (2)
00000
自然数a,bに対して, aとbが互いに素ならば、 α+b と ab は互いに素であるこ
とを証明せよ。
P.476 基本事項 2 114
a+b abの最大公約数が1となることを直接示すのは糸口を見つけにくい。
そこで、背理法 (間接証明法)を利用する。 at babが互いに素でない、すなわち
a+b と abはある素数』を公約数にもつ、と仮定して矛盾を導く。·······
なお、次の素数の性質も利用する。ただし、 は整数である。
mnが素数の倍数であるとき、またはnはの倍数である。
45
5 最大公約数が1を導く
[2] 背理法 (間接証明法) の利用
このとき、1+1は3の これはともが互いに素であることに矛盾している。
である。したがって
bがpの倍数であるときも、同様にしては』の倍数であり、
4+1-3m² と表されるから､
aとbが互いに素であることに矛盾する。
+9-8-3m-24m
したがって, a+babは互いに素である。
a+b と ab が互いに素でない、すなわちa+b と abはある素
を公約数にもつと仮定すると
a+b=pk....... ①, ab=pl....... ② (k,は自然数)
と表される。
②から、またはもは♪の倍数である。
がpの倍数であるとき,a=pm となる自然数mがある。.
このとき、①からbpk-a-pk-pm=pm となり
もの倍数である。
第6講
4mとが互いに素でない
とが数を公約
にもつ
は
© 113 (1) aとbが互いに素ならば、
da-pk-b
-p(k-m')
(mmは整数)
481
同様にして, nna(n+1)=n(n+1) (n+1) は異なる素因数を3個以上もつ、
この操作は無限に続けることができるから、素数は無限個存在する。
※各自=2や3などの場合で、このことを検証してみるとよい。
4章
αbは自然数とする。 このとき、次のことを証明せよ。
とは互いに素である。
/ (2) a+b と ab が互いに素ならば、ともは互いに素である。
17
前ページの基本例題112 (2) の結果 「連続する2つの自然数は互いに素である」は、整数
の問題を解くのに利用できることがある。 興味深い例を1つあげておこう。
1
素数は無限個あることを証明せよ。
明n を2以上の自然数とする。 とn+1は互いに素であるから, n(n+1) は異な
る素因数を2個以上もつ。
最大公約数と小数
素数が無限個あることの証明は、ユークリッドが発見した背理法を利用する方法が有名である
が、上の証明は、21世紀に入って (2006年)。 サイダックによって提示された。 とても簡潔な方
法である。
×
