整数問題bot/

「2倍して１を加える」操作を続けると：　ずっと素数になることがあるのか。（という疑問から）
　　16段続くものが発見されている。

== Sophie Germain prime ==

http://primes.utm.edu/glossary/xpage/SophieGermainPrime.html

https://en.wikipedia.org/wiki/Sophie_Germain_prime

https://oeis.org/A005384

== 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 2^11^ − 1.

Proof: Let q be 2p + 1. By Fermat's little theorem, 2^2p^ ≡ 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.

----
http://math.stackexchange.com/questions/1117319/if-p-and-q-2p-1-are-both-odd-primes-show-that-4-and-2-11-2p

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.