Editing Safe and Sophie Germain primes (section)

==Properties==
There is no special primality test for safe primes the way there is for [[Fermat prime]]s and [[Mersenne prime]]s. However, [[Pocklington primality test|Pocklington's criterion]] can be used to prove the primality of 2''p'' + 1 once one has proven the primality of ''p''. 

Just as every term except the last one of a [[Cunningham chain]] of the first kind is a Sophie Germain prime, so every term except the first of such a chain is a safe prime. Safe primes ending in 7, that is, of the form 10''n''&nbsp;+&nbsp;7, are the last terms in such chains when they occur, since 2(10''n''&nbsp;+&nbsp;7)&nbsp;+&nbsp;1 = 20''n''&nbsp;+&nbsp;15 is [[divisibility|divisible]] by 5.

For a safe prime, every [[quadratic nonresidue]], except −1 (if nonresidue{{efn|−1 is a quadratic residue only when the safe prime is equal 5; for all other safe primes, −1 is a nonresidue}}), is a [[Primitive root modulo n|primitive root]]. It follows that for a safe prime, the least positive primitive root is a prime number.<ref>{{cite journal|vauthors=Ramesh VP, Makeshwari M|title=Least Primitive Root of any Safe Prime is Prime|journal=The American Mathematical Monthly|issue=10|volume=129|date=16 September 2022|page=971 |doi=10.1080/00029890.2022.2115816}}</ref>

===Modular restrictions===
With the exception of 7, a safe prime ''q'' is of the form 6''k''&nbsp;&minus;&nbsp;1 or, equivalently, ''q'' ≡ 5 ([[modulo operation|mod]] 6) – as is ''p'' > 3. Similarly, with the exception of 5, a safe prime ''q'' is of the form 4''k''&nbsp;&minus;&nbsp;1 or, equivalently, ''q'' ≡ 3 (mod 4) — trivially true since (''q''&nbsp;&minus;&nbsp;1) / 2 must evaluate to an [[parity (mathematics)|odd]] [[natural number]]. Combining both forms using [[least common multiple|lcm]](6, 4) we determine that a safe prime ''q'' > 7 also must be of the form 12''k'' − 1 or, equivalently, ''q'' ≡ 11 (mod 12).

It follows that, for any safe prime ''q'' > 7:
* both 3 and 12 are [[quadratic residue]]s mod ''q'' (per [[Quadratic residue#Law of quadratic reciprocity|law of quadratic reciprocity]]) <!-- this wikilink to a section is used to provide easy access to the table in the section, specifically a = 3 and a = 12 rows -->
** neither 3 nor 12 is a [[Primitive root modulo n|primitive root]] of ''q''
** the only safe primes that are also [[full reptend prime]]s in [[base 12]] are 5 and 7
** ''q'' divides 3<sup>(''q''−1)/2</sup> − 1 and 12<sup>(''q''−1)/2</sup> − 1, same as 3<sup>(''q''−1)/2</sup> ≡ 1 mod ''q'' and 12<sup>(''q''−1)/2</sup> ≡ 1 mod ''q'' (per [[Euler's criterion]])
* ''q''&nbsp;−&nbsp;3, ''q''&nbsp;−&nbsp;4, ''q''&nbsp;−&nbsp;9, ''q''&nbsp;−&nbsp;12 are quadratic nonresidues <!-- see the table at  [[Quadratic residue#Law of quadratic reciprocity]] -->
** ''q''&nbsp;−&nbsp;3, ''q''&nbsp;−&nbsp;4, ''q''&nbsp;−&nbsp;9, and, for ''q'' > 11, ''q''&nbsp;−&nbsp;12 are primitive roots <!-- as all nonresidues, except −1, are primitive roots for safe primes -->
If ''p'' is a Sophie Germain prime greater than&nbsp;3, then ''p'' must be congruent to 2&nbsp;mod&nbsp;3. For, if not, it would be congruent to 1&nbsp;mod&nbsp;3 and 2''p''&nbsp;+&nbsp;1 would be congruent to 3&nbsp;mod&nbsp;3, impossible for a prime number.<ref>{{citation|title=An Episodic History of Mathematics: Mathematical Culture Through Problem Solving|publisher=Mathematical Association of America|first=Steven G.|last=Krantz|year=2010|isbn=9780883857663|page=206|url=https://books.google.com/books?id=ulmAH-6IzNoC&pg=PA206}}.</ref> Similar restrictions hold for larger prime moduli, and are the basis for the choice of the "correction factor" 2''C'' in the Hardy–Littlewood estimate on the density of the Sophie Germain primes.<ref name="shoup"/>

If a Sophie Germain prime ''p'' is [[Congruence relation|congruent]] to 3 (mod 4) ({{oeis|id=A002515}}, ''Lucasian primes''), then its matching safe prime 2''p''&nbsp;+&nbsp;1 ([[modular arithmetic|congruent]] to 7 modulo 8) will be a divisor of the [[Mersenne number]]&nbsp;2<sup>''p''</sup>&nbsp;−&nbsp;1. Historically, this result of [[Leonhard Euler]] was the first known criterion for a Mersenne number with a prime index to be [[composite number|composite]].<ref>{{citation
 | last = Ribenboim | first = P. | author-link = Paulo Ribenboim
 | doi = 10.1007/BF03023623
 | issue = 2
 | journal = [[The Mathematical Intelligencer]]
 | mr = 737682
 | pages = 28–34
 | title = 1093
 | volume = 5
 | year = 1983}}.</ref> It can be used to generate the largest Mersenne numbers (with prime indices) that are known to be composite.<ref>{{citation|title=Large Sophie Germain primes|first=Harvey|last=Dubner|author-link=Harvey Dubner|journal=Mathematics of Computation|volume=65|year=1996|issue=213 |pages=393–396|doi=10.1090/S0025-5718-96-00670-9|mr=1320893|citeseerx=10.1.1.106.2395}}.</ref>