an+1 = p an + p - 1
連續兩兩互質數列 (2)

上一篇想到的數列之後
是不是除了2之外還可以更一般化呢?

因為2是質數的第一個
於是就想到是否能夠把原本數列用任一質數p來取代2
可是又要確保首項之外每一項都是奇數
所以就用+p -1的方式來取代原本的+1

於是這個數列就可以寫成:

an+1 = p an + p - 1
a1 = p

p是任一質數

希望證明這個數列連續兩項必定互質

這個部份證明也是一樣用數學歸納法和反證法搞定

首先
要先證明 a1、a2 互質:

先假設兩者不互質
由於 a= p 是質數
所以 a2 必須是 p的倍數
假設 a2 = pk,k是正整數

又 a2 = p‧p + p - 1 = pk
即 p2 + p - pk = 1
p(p+1-k) = 1
但是 p+1-k是整數
因此不存在一個質數p
能夠使得p(p+1-k) = 1
所以 a2 不是pk
即 a1、a2 互質

確定 a1、a2 互質之後
再來就要開始數學歸納法的下一步驟

設 an、an+1 互質
然後假設 an+1、an+2 不互質
所以設
an+1 = ms
an+2 = mt
其中 m, s, t 皆為正整數
m 是 an+1 , an+2 的最大公因數且 m>1

又 an+2 = p‧an+1 + p - 1=mt --- (1)式
an+1 = p‧an     + p - 1=ms --- (2)式

(1)式-(2)式:
p‧( an+1 - an ) = m(t-s)  --- (3)式
因為 p 質數又可整除 m(t-s)
所以 p│m 或 p│(t-s)

若 p│m
則設 m = ph,h正整數
an+1 = p‧an     + p - 1 = ms = phs
p‧an     + p - 1 = phs
p‧an     + p - phs = 1
p‧(an+1-hs) = 1
因為 (an+1-hs)是整數
故不存在 質數p 能使得 p‧(an+1-hs) = 1 矛盾
所以p無法整除m
即m非p之倍數

若 p│(t-s)
令 (t-s) = pg,g正整數
代入(3)式
p‧( an+1 - an ) = mpg
約掉p
an+1 - an = mg
an+1 = ms
所以 ms - an = mg
m(s-g) = an
且因為 an > 0
所以 an 是 m的倍數
表示 an an+1 至少有公因數 m>1
與假設「 an、an+1 互質」不符
故p也無法整除(t-s)
矛盾


因此p無法整除 m 與 (t-s)
則沒有p與m能滿足(3)式
亦即不存在m

因此 an+1、an+2 互質

根據數學歸納法
此數列連續兩項必定兩兩互質!
得證



不過既然上一篇有提到隔一個也互質
就想要證明看看是否這個數列也會這樣
然而我目前還沒想到證法~


belleaya (愛) 發表在 痞客邦 PIXNET 留言(0) 人氣()