20.4.17

Why Steady Primes?

In my previous entry I discussed a subset of safe primes with an interesting property.

It appears that when a prime p is of the form 8k - 1 where 4k - 1 and 8k - 1 are both primes, then the order of each power of 2 mod p is phi(p)/2 where phi() is the Euler's Totient Function.

This is only one part of my conjecture. Here's another part of it:

Conjecture: If p is a prime of the form 8k - 1 where 4k - 1 and 8k - 1 are both primes and n is an integer smaller than q such that it is not a power of 2 mod p, then the order of n mod p is phi(p)= p-1

Example: Below is an image of the exponentiation tables of Z23 and Z7.



In my previous entry I called such primes "steady primes". The reason why I chose the name "steady" is because of the "steady", uniform structure of the exponentiation table of Zp when p is a steady prime.

All elements of Zp when p is a steady prime have order that is equal to or greater than phi(p)/2. This is also true for the rest of the safe primes, which are the tough primes, but the structure of the exponentiation table of Zp when p is a tough prime is different.  With tough primes every odd power of 2 mod p has order p-1 and every even power of 2 mod p has order phi(p)/2.

Conjecture: If p is a steady prime, then phi(p)/2 is also a prime number.

Example: The first few steady primes are: 7,23,47,167,263,359,383,479,503

phi(p)/2 when p is the first few steady primes is equal to: 3,11, 23, 83, 131, 179, 191, 239, 261

Unfortunately, the curious properties of steady primes are not applicable to all products of steady primes. There are some products of steady primes pq with such uniform structure of the exponentiation table of Zpq but they are kind of rare.

Below is a calculator that can be used to generate powers of powers of integers modulo other integers, the algorithm for which I described here.

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.