例題103 倍数,互いに素に関する証明
自然数aに対し, aとa+1は互いに素であることを証明せよ。
aは自然数とする。a+5 は4の倍数であり,a+3は6の倍数であると
OO00
本例題
389 基本事項3, 5
p.388, 389 基本事項 1,5
OLUT:
OLUTION
CHART O
倍数である,互いに素であることの証明
m, nを自然数として a+5=4m, a+3=6n と表される。そして, 「aの倍
数かつもの倍数ならば, a とbの最小公倍数の倍数」であることを利用する。
……の
とは, 2* が
………の
また,aとbが互いに素のとき「ak がbの倍数ならば, kはbの倍数」である
ことを利用してもよい (別解参照)。
(2) 互いに素である → 最大公約数が1
最大公約数をgとおいて, g=1 であることを証明すればよい。
自然数 A, Bについて AB=1 → A=B=1 を利用する。
る。
解答
(1) a+5, a+3は, 自然数 m, nを用いて
a+5=4m, a+3=6n ,
別解(1) 0, ②から
が素因数3
16 は素因
いから, n
2個もつ。
すなわち
と表される。
a+9=(a+5)+4年4m+4=4(m+1)
a+9=(a+3)+6-6n+6=6(n+1)
I よって, ① より a+9は4の倍数であり,②より a+9は6
の倍数でもある。
したがって, a+9は4と6の最小公倍数 12 の倍数である。
(2) aとa+1の最大公約数をgとすると
の
2と3は互いに素であ
から, m+1は3の倍
である。よって,
m+1=3k(kは自然
と表される。ゆえに
a+9=4(m+1)
=4·3k=12k
したがって, a+9は
倍数である。
の
因数5
は素因
a=mg, a+1=ng (m, nは互いに素な自然数)
と表される。
50は素
かもた
因数 5
a=mg を a+1=ng に代入すると
mg+1=ng
(n-m)g=1
aを消去する。
すなわち
n, m, gは自然数であるから, この等式を満たすのは,
n-m=1, g=1 の場合のみである。
したがって, aとa+1の最大公約数は1であるから, aと
a+1 は互いに素である。
linf. 0を含まない連続する2つの整数は互いに素である。
*aとa+1が負の
も,同様に成り三
OL
は4の位新であり
a+3は
hし
