A primitive root of a prime p is an integer g such that g (mod p) has modulo order p-1. More generally, if GCD(g, n) = 1 (g and n are relatively prime) and g is of modulo order modulo phi(n) mod n where phi(n) is the totient function, then g is a primitive root of n. The first definition is a special case of the second since Phi(p) = p-1 for p a prime.

Here are some notes from my program XICalc - Extra Precision Integer Calculator http://www.oocities.org/hjsmithh/download.html#XICalc :

PrimR(x) = Largest and smallest primitive root of x or 0:

The number of primitive roots (pr's) that x has is displayed. If x does not have any pr's, zero is returned. If x has only one pr, it is returned. If x has 2 or more pr's, the largest and smallest are displayed and the smallest is returned. The named number "Re" is set to the largest primitive root or 0 if x does not have any pr's. For example:

PrimRP(x) = Largest and smallest prime primitive root of x:

The number of primitive roots (pr's) that x has is displayed. If x does not have any prime pr's, zero is returned. If x has only one prime pr, it is returned. If x has 2 or more prime pr's, the largest and smallest prime pr are displayed and the smallest is returned. The named number "Re" is set to the largest prime primitive root or 0 if x does not have any prime pr's.

PrimRQ(x, y) = 1 (True) if x is a primitive root of y, else 0:

This function answers the question: Is x a primitive root of |y|?

The algorithms for PrimR(x), PrimRP(x), and PrimRQ(x, y) can be found in the C# source file PrimeFA.cs in my program XICalc. See download link above.

Return to Number Theory, Algorithms, and Real Functions

Return to Harry's Home Page

This page accessed times since Feb 17, 2006.

Page created by: hjsmithh@sbcglobal.net

Changes last made on Monday, 06-Aug-07 20:47:31 PDT