Find the number of primitive roots modulo prime

0 0 4 minutes read

Given a prime $p$ . The task is to count all the primitive roots of $p$ .
A primitive root is an integer x (1 <= x < p) such that none of the integers x – 1, x² – 1, …., x^{p – 2} – 1 are divisible by $p$ but x^{p – 1} – 1 is divisible by $p$ .
Examples:

Input: P = 3
Output: 1
The only primitive root modulo 3 is 2.
Input: P = 5
Output: 2
Primitive roots modulo 5 are 2 and 3.

Approach: There is always at least one primitive root for all primes. So, using Eulers totient function we can say that f(p-1) is the required answer where f(n) is euler totient function.
Below is the implementation of the above approach:

C++

// CPP program to find the number of
// primitive roots modulo prime
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of
// primitive roots modulo p
int countPrimitiveRoots(int p)
{
    int result = 1;
    for (int i = 2; i < p; i++)
        if (__gcd(i, p) == 1)
            result++;
 
    return result;
}
 
// Driver code
int main()
{
    int p = 5;
 
    cout << countPrimitiveRoots(p - 1);
 
    return 0;
}

Java

// Java program to find the number of
// primitive roots modulo prime
 
import java.io.*;
 
class GFG {
 // Recursive function to return gcd of a and b 
    static int __gcd(int a, int b) 
    { 
        // Everything divides 0  
        if (a == 0) 
          return b; 
        if (b == 0) 
          return a; 
        
        // base case 
        if (a == b) 
            return a; 
        
        // a is greater 
        if (a > b) 
            return __gcd(a-b, b); 
        return __gcd(a, b-a); 
    } 
 
// Function to return the count of
// primitive roots modulo p
static int countPrimitiveRoots(int p)
{
    int result = 1;
    for (int i = 2; i < p; i++)
        if (__gcd(i, p) == 1)
            result++;
 
    return result;
}
 
// Driver code
    public static void main (String[] args) {
            int p = 5;
 
    System.out.println( countPrimitiveRoots(p - 1));
    }
}
// This code is contributed by anuj_67..

Python3

# Python 3 program to find the number 
# of primitive roots modulo prime
from math import gcd
 
# Function to return the count of
# primitive roots modulo p
def countPrimitiveRoots(p):
    result = 1
    for i in range(2, p, 1):
        if (gcd(i, p) == 1):
            result += 1
 
    return result
 
# Driver code
if __name__ == '__main__':
    p = 5
 
    print(countPrimitiveRoots(p - 1))
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# program to find the number of 
// primitive roots modulo prime 
   
using System;
   
class GFG { 
 // Recursive function to return gcd of a and b  
    static int __gcd(int a, int b)  
    {  
        // Everything divides 0   
        if (a == 0)  
          return b;  
        if (b == 0)  
          return a;  
          
        // base case  
        if (a == b)  
            return a;  
          
        // a is greater  
        if (a > b)  
            return __gcd(a-b, b);  
        return __gcd(a, b-a);  
    }  
   
// Function to return the count of 
// primitive roots modulo p 
static int countPrimitiveRoots(int p) 
{ 
    int result = 1; 
    for (int i = 2; i < p; i++) 
        if (__gcd(i, p) == 1) 
            result++; 
   
    return result; 
} 
   
// Driver code 
     static public void Main (String []args) { 
            int p = 5; 
   
    Console.WriteLine( countPrimitiveRoots(p - 1)); 
    } 
} 
// This code is contributed by Arnab Kundu

PHP

<?php
// PHP program to find the number of
// primitive roots modulo prime
 
// Recursive function to return
// gcd of a and b 
function __gcd($a, $b) 
{ 
    // Everything divides 0 
    if ($a == 0) 
    return b; 
     
    if ($b == 0) 
    return $a; 
     
    // base case 
    if ($a == $b) 
        return $a; 
     
    // a is greater 
    if ($a > $b) 
        return __gcd($a - $b, $b); 
    return __gcd($a, $b - $a); 
} 
 
// Function to return the count of
// primitive roots modulo p
function countPrimitiveRoots($p)
{
    $result = 1;
    for ($i = 2; $i < $p; $i++)
        if (__gcd($i, $p) == 1)
            $result++;
 
    return $result;
}
 
// Driver code
$p = 5;
 
echo countPrimitiveRoots($p - 1);
 
// This code is contributed by anuj_67
?>

Javascript

<script>
 
// Javascript program to find the number of
// primitive roots modulo prime
 
 // Recursive function to return gcd of a and b  
 function __gcd( a,  b)  
 {  
     // Everything divides 0   
     if (a == 0)  
       return b;  
     if (b == 0)  
       return a;  
       
     // base case  
     if (a == b)  
         return a;  
       
     // a is greater  
     if (a > b)  
         return __gcd(a-b, b);  
     return __gcd(a, b-a);  
 }  
   
 
// Function to return the count of
// primitive roots modulo p
function countPrimitiveRoots(p)
{
    var result = 1;
    for (var i = 2; i < p; i++)
        if (__gcd(i, p) == 1)
            result++;
 
    return result;
}
 
// Driver code
var p = 5;
document.write( countPrimitiveRoots(p - 1));
 
</script>

Output:

Time Complexity: O(p * log(min(a, b))), where a and b are two parameters of gcd.

Auxiliary Space: O(log(min(a, b)))

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!