-
![]()
-
![]()
基本例題113 互いに素に関する証明問題 (2)
00000
自然数a,bに対して, aとbが互いに素ならば, a + b と abは互いに素であるこ
とを証明せよ。
091 5:
指針a+b と ab の最大公約数が1となることを直接示すのは糸口を見つけにくい。
そこで,背理法(間接証明法)を利用する。→a+b と ab が互いに素でない,すなわち
a+b と ab はある素数を公約数にもつ,と仮定して矛盾を導く。
なお、次の素数の性質も利用する。 ただし,m,nは整数である。
mnが素数」の倍数であるとき, mまたはnはかの倍数である。
CHART 互いに素であることの証明
解答
a+b と ab が互いに素でない,すなわち a + b と ab はある素
数』を公約数にもつと仮定すると
a+b=pk
①, ab=pl
......
p.4762 重要 114
①1 最大公約数が1を導く
2 背理法 (間接証明法) の利用
② , lは自然数)
to
と表される。
② から, a または6の倍数である。
aがpの倍数であるとき, a=pmとなる自然数mがある。
このとき、①から6=pk-a=pk-pm=p(k-m) となり,
bもpの倍数である。
これはαとが互いに素であることに矛盾している。
bがpの倍数であるときも、同様にしてαはかの倍数であり,
aとbが互いに素であることに矛盾する。
したがって, a +6 と ab は互いに素である。
[番号] 前ページの基本例題 112 (2) の結果 「連続する2つの自然数は互いに素である」は、整数
この問題を解くのに利用できることがある。 興味深い例を1つあげておこう。
各自=2や 3 などの場合で,このことを検証してみるとよい。
n₁
mとnが互いに素でない
⇔mとnが素数を公約
数にもつ
k-mは整数。
TRAF
a=pk-b
問題 素数は無限個あることを証明せよ。
[証明]
n を2以上の自然数とする。 と+1は互いに素であるから, n2 =n(n+1) は異な
る素因数を2個以上もつ。
同様にして。 ns=n(n+1)=n(n+1)(n2+1) は異なる素因数を3個以上もつ。
この操作は無限に続けることができるから、素数は無限個存在する。
=p(k-m')
( m' は整数)
素数が無限個あることの証明は,ユークリッドが発見した背理法を利用する方法が有名である
け 21世紀に入って (2006年), サイダックによって提示された, とても簡潔な方
a)(w)
P
481
4章
17
約数と倍数、最大公約数と最小公倍数
