Write Script to Calculate Number of Primitive Roots

What Are Primitive Roots?

A primitive root modulo n is an integer g that is a generator of the multiplicative group of integers modulo n. This means that the powers of g modulo n produce all the integers from 1 to φ(n), where φ is Euler's totient function.

For a number n, a primitive root exists if and only if n is 2, 4, p^k, or 2p^k, where p is an odd prime number and k is a positive integer.

How to Calculate Number of Primitive Roots

The number of primitive roots modulo n is equal to φ(φ(n)), where φ is Euler's totient function. This is because the number of generators (primitive roots) of a cyclic group of order φ(n) is φ(φ(n)).

To calculate this:

1. First compute φ(n), the Euler's totient function of n.
2. Then compute φ(φ(n)), the Euler's totient function of the result from step 1.
3. The result is the number of primitive roots modulo n.

Here's how Euler's totient function works:

• If n is a prime number, φ(n) = n - 1.
• If n is a power of a prime p, φ(p^k) = p^k - p^(k-1).
• For two coprime numbers a and b, φ(ab) = φ(a)φ(b).

JavaScript Implementation

Here's a JavaScript function to calculate the number of primitive roots modulo n:

function gcd(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

function eulerTotient(n) {
    if (n === 1) return 1;

    let result = n;
    for (let p = 2; p * p <= n; p++) {
        if (n % p === 0) {
            while (n % p === 0) {
                n /= p;
            }
            result -= result / p;
        }
    }

    if (n > 1) {
        result -= result / n;
    }

    return result;
}

function numberOfPrimitiveRoots(n) {
    if (n === 1) return 0;

    // Check if n is 2, 4, p^k, or 2p^k
    let temp = n;
    if (temp % 2 === 0) {
        temp /= 2;
    }

    let isValid = true;
    if (temp === 1) {
        // n is 2 or 4
        return 1;
    } else {
        // Check if temp is a power of an odd prime
        for (let p = 3; p * p <= temp; p += 2) {
            if (temp % p === 0) {
                while (temp % p === 0) {
                    temp /= p;
                }
                if (temp !== 1) {
                    isValid = false;
                    break;
                }
            }
        }
        if (temp > 2) {
            isValid = false;
        }
    }

    if (!isValid) {
        return 0;
    }

    const phiN = eulerTotient(n);
    return eulerTotient(phiN);
}

The function first checks if n has primitive roots, then calculates φ(n) and φ(φ(n)) to determine the number of primitive roots.

Examples

Let's look at some examples to understand how this works:

Example 1: n = 7 (a prime number)

Since 7 is prime, φ(7) = 6. Then φ(6) = 2. So there are 2 primitive roots modulo 7.

Example 2: n = 8

8 is not of the form 2, 4, p^k, or 2p^k, so it doesn't have primitive roots. The function returns 0.

Example 3: n = 9 (3^2)

φ(9) = 6. Then φ(6) = 2. So there are 2 primitive roots modulo 9.

Example 4: n = 10

10 is not of the required form, so it doesn't have primitive roots. The function returns 0.