Carmichael猜想的一個(gè)標(biāo)注

王恒洲, 史三英

(合肥工業(yè)大學(xué) 數(shù)學(xué)學(xué)院,安徽 合肥 230601)

對(duì)于任意整數(shù)x,文獻(xiàn)[1]證明了關(guān)于未知數(shù)n的方程φ(n)=x解的個(gè)數(shù)不為1，但是文獻(xiàn)[1]的證明被發(fā)現(xiàn)存在錯(cuò)誤,這個(gè)斷言便被稱為Carmichael猜想；文獻(xiàn)[2]證明了當(dāng)x<1037時(shí),該猜想是成立的；文獻(xiàn)[3]將這個(gè)界提高到10400；文獻(xiàn)[4-5]分別將上界提高到1010 000、10107。目前10108仍是最好的結(jié)果。

文獻(xiàn)[6]證明了反例的一個(gè)充分條件,即如果對(duì)于每一個(gè)使得p-1整除φ(n)的素?cái)?shù)p都有p2|φ(n),那么n就是一個(gè)反例。

文獻(xiàn)[7]證明猜想成立當(dāng)且僅當(dāng)

其中

E1(x)=#{n|1≤n

E(x)=#{n|1≤n0}；

A(m)=#{n|φ(n)=m}。

文獻(xiàn)[7]還證明了E1(x)=101010。

關(guān)于A(m)值域的研究是Carmichael猜想的一個(gè)重要的延伸課題。文獻(xiàn)[8]證明了任意非1的正整數(shù)都屬于A(m)的值域。

本文中p和q總是表示素?cái)?shù),P(x)表示x的所有素因數(shù)集,S(x)表示滿足p-1整除x的全體p的集合。定義vp(x)為p整除x的最高指數(shù),即pvp(x)‖x。

定義1 若T(x)?S(x),并滿足:

當(dāng)p∈T(x)∩P(x)時(shí),有

當(dāng)p∈P(x)-T(x)時(shí),有

則稱T(x)為S(x)的一個(gè)φ-子集。

定義N(x)是方程φ(n)=x的關(guān)于未知數(shù)n的解數(shù),則Carmichael猜想成立等價(jià)于N(x)≠1。本文將證明下面的定理。

定理1N(x)等于S(x)的φ-子集的個(gè)數(shù)。

定理2 Carmichael猜想的成立當(dāng)且僅當(dāng)該猜想在集{24337243k,k為任意正整數(shù)}上成立。

1 定理1的證明

(1) 下面將證明對(duì)于S(x)不同的φ-子集,都能找到不同的n,滿足φ(n)=x。假設(shè)T(x)是S(x)的一個(gè)φ-子集,由定義可得:

由算術(shù)基本定理可得,當(dāng)T1(x)≠T(x)時(shí),存在n1≠n,滿足φ(n1)=φ(n2)。

由上述可知,對(duì)于S(x)不同的φ-子集,都能找到不同的n滿足φ(n)=x。

x=φ(n)=

令T′(x)={p1,p2,…,pt},可得:

對(duì)于p∈P(x)∩T′(x),則有：

對(duì)于p∈P(x)-T′(x),則有：

則由定義1可知T′(x)是S(x)的φ-子集。

由算術(shù)基本定理可知,若存在一個(gè)不等于n的m滿足φ(m)=x,則S(x)存在一個(gè)不等于T′(x)的φ-子集。

由(1)、(2)可得,對(duì)于任意滿足φ(m)=x的正整數(shù)n,都能唯一地構(gòu)造S(x)的φ-子集。

推論1 若偶數(shù)x滿足S(x)=P(x),且當(dāng)p∈P(x)時(shí),有

則N(x)=1。

證明由S(x)=P(x)條件可知,S(x)是本身的一個(gè)φ-子集。對(duì)于S(x)的任意真子集S1(x),令p0∈P(x)-S1(x),可得:

因此,S(x)的任意子集都不會(huì)是S(x)的φ-子集。故S(x)只有一個(gè)φ-子集,即N(x)=1,也就是說(shuō)x=φ(n)是Carmichael猜想的一個(gè)反例。

2 φ -子集的構(gòu)造

令T(x)是S(x)的一個(gè)φ-子集,ρ是T(x)∩P(x)子集,且滿足:

2.1 添加一個(gè)元素到φ -子集生成新的φ -子集

若p∈T(x)∪{q0}∩P(x),則

vp(q0-1)=0。

由定義1可知,T(x)∪{q0}也是S(x)的φ-子集。

由上述可知,當(dāng)S(x1)?T(x)時(shí),可以通過(guò)添加一個(gè)元素來(lái)生成新的φ-子集。

2.2 從φ -子集刪除一個(gè)元素生成新的φ -子集

定義Tρ(x)={q|P(q-1)?ρ}∩T(x)。當(dāng)Tρ(x)?ρ時(shí), 取q0∈Tρ(x)-ρ,易證T(x)-{q0}也是S(x)的φ-子集,這是因?yàn)閷?duì)于p∈P(x)∩(T(x)-{q0}),有

對(duì)于p∈P(x)-(T(x)-{q0}), 定義1得到滿足。

綜上所述,當(dāng)Tρ(x)?ρ時(shí),可以從φ-子集刪除一個(gè)元素生成新的φ-子集。

顯然可得,當(dāng)S(x)存在一個(gè)滿足以上2個(gè)條件的φ-子集時(shí),N(x)≠1。下面將研究不滿足上述2個(gè)條件的φ-子集,即無(wú)法通過(guò)上述2個(gè)方法生成新的φ-子集的T(x)。

3 定理2的證明

3.1 相關(guān)引理的證明

為了證明定理2,需要先證明下面的2個(gè)引理。

引理1 Carmichael猜想成立當(dāng)且僅當(dāng)猜想在集合S(x)上成立。

(1) 假設(shè)S(x)只有一個(gè)φ-子集T(x),則T(x)無(wú)法通過(guò)上述刪除一個(gè)元素生成新的φ-子集。

當(dāng)Tρ(x)=T(x)時(shí),有

T(x)=Tp(x)?ρ=P(x),

P(x)?ρ?T(x),

因此x∈T1。

當(dāng)Tρ(x)≠T(x)時(shí),令

由x1的定義可得:

Tp(x)?ρ,

P(x1)?ρ?T(x),

S(x1)?Sp(x),

定義Sρ(x)={q|P(q-1)?ρ}∩S(x),則有：

S(x1)∩P(x1)?T(x)∩Sρ(x)=Tρ(x)。

另一方面,因?yàn)門(mén)ρ(x)?S(x1)∩P(x1),所以Tρ(x)=S(x1)∩P(x1)。這說(shuō)明Tρ(x)也不能通過(guò)刪除一個(gè)元素來(lái)生成新的φ-子集。于是可以令T(x1)=Tρ(x)。這時(shí),如果x1?T1,可以重復(fù)步驟取x2,這些步驟是會(huì)終止的。因?yàn)門(mén)(xn)?T(xn-1)且1∈T1，所以存在一個(gè)xN滿足xN∈T1。

如果存在只有一個(gè)φ-子集的S(x),那么存在一個(gè)數(shù)xN,滿足xN∈T1。

(2) 假設(shè)xn和T(xn)由上述步驟得到,且T1(xn)是S(xn)不同與T(xn)的另一個(gè)φ-子集。

情形1 當(dāng)T1(xn)∩T(xn-1)=?時(shí),對(duì)任意素?cái)?shù)p∈P(xn-1),有

特別地,當(dāng)p∈P(xn-1)-T(xn-1)時(shí),因?yàn)門(mén)(xn)?T(xn-1),所以p∈P(xn)-T(xn)。

若p∈P(xn)-T1(xn),可得:

vp(xn)+vp(xn-1)-vp(xn)=vp(xn-1)。

若p∈P(xn) ∩T1(xn),則

T1(xn)∩T(xn-1)=?,

這與T1(xn)∩T(xn-1)=?相矛盾。

這就證明了T1(xn)∪(T(xn-1)-T(xn))是S(xn-1)的不同于T(xn-1)的φ-子集。

情形2 當(dāng)T1(xn)∩T(xn-1)≠?時(shí),有

T(xn-1)∩T1(xn)?

T(xn-1)∩S(xn)?

T(xn-1)∩Sρ(xn-1)=T(xn),

因此T1(xn)∩(T(xn-1)-T(xn))=?。

同理可得,T1(xn)∪(T(xn-1)-T(xn))是S(xn-1)的不同于T(xn-1)的φ-子集。

由以上討論可知,如果S(xn)存在一個(gè)不同于T(xn)的φ-子集T(xn-1),那么S(xn-1)也存在一個(gè)不同于T(xn-1)的φ-子集。

綜合(1)、(2)可知,如果存在S(x)只有一個(gè)φ-子集,那么就一定存在一個(gè)數(shù)xN∈T1,使得S(xN)也只有一個(gè)φ-子集,即若猜想在集合T1成立,則猜想成立。即引理1得證。

定義2

P(x′)=P(x)且S(x′)?P(x′)}。

引理2 Carmichael猜想成立當(dāng)且僅當(dāng)猜想在T上集合成立。

證明若T(x)無(wú)法通過(guò)添加一個(gè)元素來(lái)生成新的φ-子集,則S(x′)?P(x)=P(x′)。

結(jié)合引理1,引理2得證。

3.2 定理2的證明

證明因?yàn)閷?duì)于任意x∈T,都有：

2∈S(x′)?P(x′)=P(x),

所以由定義2可得:

3∈S(x′)?P(x′)=P(x)。

以此類(lèi)推,可得:

7∈S(x′)?P(x′)=P(x)，

43∈S(x′)?P(x′)=P(x)。

于是有：

{2,3,7,43}?P(x′)=P(x)。

故由x∈T可得,24337243|x。

由引理2,定理2得證。