20.4.17

Steady Primes

Another interesting subset of the set of safe primes is the set of steady primes as defined below:

Definition: A steady prime is a safe prime p such that all powers of 2 mod p have order phi(p)/2 where phi() is Euler's Totient Function.

Example:  Let p = 23.

Using a calculator, it is easy to see that all unique powers of 2 mod 23 are 2,4,8,16,9,18,13,3,6,12,1 

Using another calculator, it is also easy to verify that the order of 2 mod 23, or the smallest integer k for which 2^k = 1 mod 23 is 11, the order of 4 mod 23 is also 11,  and so is the order of 8 mod 23, and this is the case for every other power of 2 mod 23 in the list above.

The first steady primes are 7,23,47,167,263,359,383,479,503,...

Conjecture: Steady primes are primes of the form 8p-1 such that 4p-1 and 8p-1 are also primes.

Claim: Given two steady primes p and q, the order of every power of 2 mod p*q is phi(p*q)/4

Claim: For all other safe primes q that are not steady primes, the order of at least one power of 2 mod q is at least 2 times less than the order of 2 mod q itself.

Below is a calculator for finding powers of any integer a mod n such that a < n.