7.3.16

Highest Order

Definition: The highest order of an element mod n is the order k of any element(s) such that k is equal to the least universal exponent mod n.

Note: least universal exponent as defined on page 268 in Rosen, K. Number Theory And Its Applications, 2005

Example: Given a pair of odd primes (p = a1*r + 1, q = a2*s + 1), then the highest order mod p*q is phi(p*q)/GCD(a1, a2)

Example: Given an odd prime p then the highest order is phi(p), same goes for a power of a prime, or 2 times any prime or 2 times any power of a prime.

Example: In here I conjectured that if p and q are safe primes (ie primes of the form 2s+1 where s is also a prime) such that at least one of p, q is not congruent to -1 mod 8 (I called these tough primes) then 2 mod p*q is phi(p*q)/2 which is the highest order possible mod p*q

Conjecture: Given an odd prime p then 2 mod p is of highest order if p is a tough prime.

Conjecture: Given a power of an odd prime p^t then 2 mod p^t  is of highest order if p is a tough prime.