首先有以下引理:
若正整數(shù)a,m,x,y滿足m | a^x-1,m | a^y-1,設d = (x,y) (最大公約數(shù)),則m | a^d-1.
證明:由裴蜀定理,存在正整數(shù)u,v使ux-vy = d.
由m | a^x-1,有m | a^(ux)-1 = a^(vy+d)-1.
又由m | a^y-1,有m | a^(vy)-1,故m | a^(vy+d)-a^d.
相減即得m | a^d-1.
回到原題,由q | a^p+1,有q與a互素.
q是素數(shù),由Fermat小定理有q | a^(q-1)-1.
又由q | a^p+1,有q | a^(2p)-1 = (a^p+1)(a^p-1).
設d = (2p,q-1),由引理得q | a^d-1.
由d是2p的約數(shù),p為素數(shù),故d = 1,2,p或2p.
若d = 1,有q | a-1,可得q | a^p-1,但q | a^p+1,于是q | 2,與q為奇素數(shù)矛盾.
若d = 2,有q | a^2-1 = (a+1)(a-1),而上面已證q不整除a-1,因此有q | a+1.
若d = p,有q | a^p-1,但q | a^p+1,同樣得q | 2,與q為奇素數(shù)矛盾.
若d = 2p,由d = (2p,q-1) | q-1,得存在整數(shù)k使q-1 = 2kp,即q = 2kp+1.
綜上,有q | a+1或存在整數(shù)k使q = 2kp+1.