Editing Safe and Sophie Germain primes (section)

===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>