Primitive Roots

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.

See: Primitive Root -- From MathWorld
And: Modulo Order -- From MathWorld
And: Multiplicative Order -- From MathWorld
And: Wolfram Mathematica Documentation

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:

Command: X = PrimR(41)

The prime number 41
has 16 primitive roots, the largest is 35 = n - 6, the smallest is 6

X = 6

Command: Re=

Re = 35

Command: X = PrimR(137842)

The non-prime number 1,37842 = 2^1 * 41^3
has 26240 primitive roots, the largest is 1,37835 = n - 7, the smallest is 7

X = 7

Command: Re=

Re = 1,37835
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