Question

数学原根问题

如果a有order 3 (mod P), 证明 a+1 有 order 6 (mod P)

Answer 1

ord(a)=3(modp),所以a^3=1(modp) 或者说(a-1)(a^2+a+1)=0(modp)
a-1≠0(modp)否则，ord(a)=1(modp)，从而a^2+a+1=0(modp).

于是(a+1)^6=a^6+6a^5+15a^4+20a^3+15a^2+6a+1=21(a^2+a+1)+1=1(modp)

只要说明ord(a+1)≠1,2,3(modp)即可。
若ord(a+1)=1(modp),则a=0(modp)显然不可能。
若ord(a+1)=2(modp),则a^2+2a+1=a=1(modp)也不对。
若ord(a+1)=3(modp),则a^3+3a^2+3a+1=1+3(a^2+a+1-1)+1=-1=1(modp),p=2也不可能。