首先有以下引理:
若正整数a,m,x,y满足m | a^x-1,m | a^y-1,设d = (x,y) (最大公约数),则m | a^d-1.
证明:由裴蜀定理,存在正整数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是素数,由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的约数,p为素数,故d = 1,2,p或2p.
若d = 1,有q | a-1,可得q | a^p-1,但q | a^p+1,于是q | 2,与q为奇素数矛盾.
若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为奇素数矛盾.
若d = 2p,由d = (2p,q-1) | q-1,得存在整数k使q-1 = 2kp,即q = 2kp+1.
综上,有q | a+1或存在整数k使q = 2kp+1.