梅森数（Mersenne number）是指形如 2n−12^n - 1 的正整数，记作 MnM_n。
如果梅森数本身也是一个素数，那么它就被称为梅森素数（Mersenne Prime）。
带余除法
Mp mod Mq=Mp mod qM_p\bmod M_q=M_{p\bmod q}
证明：考虑模 2q−12^{q}-1 的运算，有 2q≡1(mod2q−1)2^{q}\equiv 1 \pmod{2^q-1}
2p−1=2p mod q2kq−1≡2p mod q−1(mod2q−1)2^{p}-1=2^{p\bmod q}2^{kq}-1 \equiv2^{p\bmod q}-1 \pmod{2^q-1}
最大公约数
(Mp,Mq)=M(p,q)(M_p,M_q)=M_{(p,q)}
证明：由上述带余除法辗转相除法得到.
假设 p>qp>q，2p−1=k(2q−1)+2p mod q−12^p-1=k(2^q-1)+2^{p\bmod q}-1
合数
若 nn 为合数，则2n−12^n - 1 是合数.
证明
利用指数的性质，当 nn 是合数时，假设 n=a⋅bn = a \cdot b，其中 a,b>1a, b > 1。我们可以写：
2n−1=2a⋅b−1.2^n - 1 = 2^{a \cdot b} - 1.
使用完全幂因式分解公式：
xmn−1=(xn−1)(xn(m−1)+xn(m−2)+⋯+xn+1).x^{mn} - 1 = (x^n - 1)(x^{n(m-1)} + x^{n(m-2)} + \cdots + x^n + 1).
将 x=2x = 2、m=bm = b、n=an = a 代入，得到：
2ab−1=(2a−1)(2a(b−1)+2a(b−2)+⋯+2a+1).2^{ab} - 1 = (2^a - 1) \left( 2^{a(b-1)} + 2^{a(b-2)} + \cdots + 2^a + 1 \right).
因此，2n−12^n - 1 可分解为两个因数，且这两个因数都大于 1，说明 2n−12^n - 1 是合数。
示例验证
示例 1：n=4n = 4（合数）
2n−1=24−1=16−1=15.2^n - 1 = 2^4 - 1 = 16 - 1 = 15.
因式分解：
15=3⋅5,15 = 3 \cdot 5,
是合数。
示例 2：n=6n = 6（合数）
2n−1=26−1=64−1=63.2^n - 1 = 2^6 - 1 = 64 - 1 = 63.
因式分解：
63=3⋅3⋅7,63 = 3 \cdot 3 \cdot 7,
是合数。
示例 3：n=9n = 9（合数）
2n−1=29−1=512−1=511.2^n - 1 = 2^9 - 1 = 512 - 1 = 511.
因式分解：
511=7⋅73,511 = 7 \cdot 73,
是合数。
素数
若 2n−12^n - 1 是素数，则指数 nn 也是素数；反之，当 nn 是素数时，2n−12^n - 1 却未必是素数.
https://zhuanlan.zhihu.com/p/421078487
例如：
M7=127M_7=127 是素数.
M11=2047=23×89M_{11}=2047=23\times 89.
梅森数的奇素因子为 2kp+12kp+1 型
梅森数 2p−12^p - 1 的奇素因子 qq 为 2kp+12kp+1 型.
证明：
奇素因子 q∣2p−1q\mid 2^p - 1，所以
2p≡1(modq)2^p\equiv 1 \pmod{q}
所以 22 的阶为 pp，所以 p∣φ(q)=q−1p\mid \varphi(q)= q-1.
所以 q−1=k0pq-1=k_0p，又因为 q−1q-1 为偶数，所以 q−1=2kpq-1=2kp，所以 q=2kp+1q=2kp+1.