Find A prime p is called a Sophie Germain prime iff both p and q := 2p + 1 are p

Question

Find

A prime p is called a Sophie Germain prime iff both p and q := 2p + 1 are primes. *Enumerate all Sophie Germain primes less than 20. *prove that all Sophie Germain primes except 3 satisfy p -1 (mod 3). *For the Sophie Germain primes which are p 1 (mod 4), determine (p mod 12). Convince yourself that q 3 (mod 8). Enumerate all pairs (p, q) with p 100. *For the Sophie Germain primes which are p 3 (mod 4), determine (p mod 12). Convince yourself that q -1 (mod 8). Enumerate all pairs (p, q) with p 100.

Explanation / Answer

* 2,3,5 and 11

* two possible cases p=1(mod 3) or p=-1(mod 3)...in first case 2p+1=0(mod 3).so p=-1(mod 3).

* p=1(mod 4)=>p=4k+1=>q=8k+3=>q=3(mod 8).and p=5(mod 12).....5 pairs

* p=3(mod 4)=>p=4k+3=>q=8k+7=>q=-1(mod 8).and p=-1(mod 12)....4 pairs

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.