## 25.2.16

### Tough Primes

I was looking at the set of products of safe primes and I came across an interesting observation. The following are the set of products of safe primes p*q, followed by the set of phi(p*q), and finally the set of the order of 2 mod p*q:

p*q = [5*7=35, 5*11=55, 7*11=77, 5*23= 115, 7*23 = 161, 5*47 = 235, 11*23 = 253, 5*59 = 295,  7*47 = 329, 7*59 = 413, 5*83 = 415, 11*47 = 517, 5*107 = 535, 7*83 = 581, 7*107 = 749, 5*167 = 835, 5*179 = 895, 23*47 =1081, 5*227 = 1135, 7*167 = 1169, 7*179 = 1253, 5*263 = 1315, 7*227 = 1589,...]

phi(p*q) = [24, 40, 60, 88, 132, 184, 220, 232, 276, 348, 328, 460, 424, 492, 636, 664, 712, 1012, 904, 996, 1068, 1048, 1356,..]

order of 2 mod p*q = [12, 20, 30, 44, 33, 92, 110, 116, 69, 174, 164, 230, 212, 246, 318, 332, 356, 253, 452, 249, 534, 524, 678]

A few things popped up right away and led to the following definition:

Definition: Tough primes are primes q of the form 2p + 1 where p is a Sophie Germain prime such that q cannot also be represented as 8n + 7 for some n in Z.

In other words the set of tough primes is the set of safe primes without its intersection with the set of primes of the form 8n + 7 for some n in Z

The first few tough primes are 5, 11, 59, 83, 107, 179, 227, 347

The motivation behind defining tough primes is the following conjecture:

Conjecture: The order of 2 mod p*q when p and q are tough primes is precisely phi(p*q)/2

Edit: The order of 2 mod p*q for a tough prime p and a safe prime q that can also be represented as 8n+7 is also phi(p*q)/2.