PRIMROOT

This function returns a primitive root modulo p when the multiplicative group modulo p is cyclic.

A primitive root g modulo p generates all invertible residue classes, equivalently:

\operatorname{ord}_p(g) = \varphi(p)

Primitive roots exist only for moduli of the form 2, 4, q^e, or 2q^e where q is an odd prime.

Excel Usage

=PRIMROOT(p, smallest)

p (int, required): Modulus greater than one.
smallest (bool, optional, default: true): If true, return the smallest primitive root.

Returns (int): A primitive root modulo p.

Example 1: Primitive root for a prime modulus

Inputs:

p	smallest
19	true

Excel formula:

=PRIMROOT(19, TRUE)

Expected output:

2

Example 2: Primitive root for another prime modulus

Inputs:

p	smallest
29	true

Excel formula:

=PRIMROOT(29, TRUE)

Expected output:

2

Example 3: Primitive root without smallest constraint

Inputs:

p	smallest
50	false

Excel formula:

=PRIMROOT(50, FALSE)

Expected output:

27

Example 4: Primitive root for power of two modulus

Inputs:

p	smallest
4	true

Excel formula:

=PRIMROOT(4, TRUE)

Expected output:

3

Python Code

from sympy import primitive_root as sympy_primitive_root

def primroot(p, smallest=True):
    """
    Find a primitive root modulo n when one exists.

    See: https://docs.sympy.org/latest/modules/ntheory.html#sympy.ntheory.residue_ntheory.primitive_root

    This example function is provided as-is without any representation of accuracy.

    Args:
        p (int): Modulus greater than one.
        smallest (bool, optional): If true, return the smallest primitive root. Default is True.

    Returns:
        int: A primitive root modulo p.
    """
    try:
        root = sympy_primitive_root(p, smallest=smallest)
        if root is None:
            return "Error: No primitive root exists for the given modulus"
        return int(root)
    except Exception as e:
        return f"Error: {str(e)}"

Online Calculator

p *

Modulus greater than one.

smallest

If true, return the smallest primitive root.