# 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.