整数問題bot/
「2倍して１を加える」操作を続けると： ずっと素数になることがあるのか。（という疑問から）
- 16段続くものが発見されている。
1. Sophie Germain prime
http://primes.utm.edu/glossary/xpage/SophieGermainPrime.html
https://en.wikipedia.org/wiki/Sophie_Germain_prime
2. CunninghamChain
http://primes.utm.edu/glossary/xpage/CunninghamChain.html
- infinite chains are known to be impossible.[14]
Long Chains of Nearly Doubled Primes http://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0979939-8/S0025-5718-1989-0979939-8.pdf
- これを読めば、2倍して1増やすことで、いつかは合成数になるという証明ができそう。
p and 2p + 1 are both prime (meaning that p is a Sophie Germain prime)
if p = 3 (mod 4) and p > 3, then the prime 2p+1 divides the Mersenne number Mp.
Example: 11 and 23 are both prime, and 11 = 2 × 4 + 3, so 23 divides 211 − 1.
Proof: Let q be 2p + 1. By Fermat's little theorem, 22p ≡ 1 (mod q), so either 2p ≡ 1 (mod q) or 2p ≡ −1 (mod q).
Supposing latter true, then 2p + 1 = (21/2(p + 1))2 ≡ −2 (mod q), so −2 would be a quadratic residue mod q. However, since p is congruent to 3 (mod 4), q is congruent to 7 (mod 8) and therefore 2 is a quadratic residue mod q. Also since q is congruent to 3 (mod 4), −1 is a quadratic nonresidue mod q, so −2 is the product of a residue and a nonresidue and hence it is a nonresidue, which is a contradiction.
Hence, the former congruence must be true and 2p + 1 divides Mp.
p and 2p+1 are Sophie Germain primes if and only if p is prime and 2^(2p) == 1 (mod 2p+1).
- - Vincenzo Librandi, Oct 09 2012
Euler and Lagrange proved that if we also have p = 3 (mod 4) and p > 3, then 2p+1 is prime (and p is a Sophie Germain prime) if and only if 2p+1 divides the Mersenne Mp.