p是奇素数这个条件有点多余, 其实对奇数都成立.
证明用到平方剩余的一个结果:
引理: 对奇素数q, 若2是mod q的平方剩余 (即存在整数a使a² = 2(mod q)), 则q = ±1(mod 8).
由条件2^p = 1(mod q), 即有2^(p+1) = 2(mod q).
而p是奇数, 可取a = 2^((p+1)/2), 则a² = 2(mod q), 2是mod q的平方剩余.
于是q = ±1(mod 8).
如果需要补充引理的证明, 请追问.
p=3时，显然。
p≥4时
2^p-1=(2-1)[2^(p-1)+2^(p-2)+......+2^3+2^2+2+1]（因式分解）
=[2^(p-1)+2^(p-2)+......+2^3]+7
=8[2^(p-4)+....+1]+（8-1）
所以
2^p-1对一切不小于3 的自然数p，都与-1同余（模8）
自然，对一切奇素数p，也都与-1同余（模8）
内容全部来源于网络收集，如有侵权，请联系网站删除!