Primitive root of a prime number n modulo n in C++

In this problem, we are given a prime number N. our task is to print the primitive root of prime number N modulo N.

Primitive root of prime number N is an integer x lying between [1, n-1] such that all values of xk (mod n) where k lies in [0, n-2] are unique.

Let’s take an example to understand the problem,

Input: 13 Output: 2

To solve this problem, we have to use mathematical function called Euler’s Totient Function.

Euler’s Totient Function is the count of numbers from 1 to n which are relatively prime to the number n.

A number i is relatively prime if GCD (i, n) = 1.

In solution, if the multiplicative order of x modulo n is equal to Euler’s Totient Function, then the number is primitive root otherwise not. We will check for all relative primes.

Note: Euler’s Totient Function of a prime number n=n-1

The below code will show the implementation of our solution,

Example

 Live Demo

#include<bits/stdc++.h> using namespace std; bool isPrimeNumber(int n) {    if (n <= 1) return false;    if (n <= 3) return true;    if (n%2 == 0 || n%3 == 0) return false;    for (int i=5; i*i<=n; i=i+6)       if (n%i == 0 || n%(i+2) == 0)          return false;    return true; } int power(int x, unsigned int y, int p) {    int res = 1;    x = x % p;    while (y > 0){       if (y & 1)       res = (res*x) % p;       y = y >> 1;       x = (x*x) % p;    }    return res; } void GeneratePrimes(unordered_set<int> &s, int n) {    while (n%2 == 0){       s.insert(2);       n = n/2;    }    for (int i = 3; i <= sqrt(n); i = i+2){       while (n%i == 0){          s.insert(i);          n = n/i;       }    }    if (n > 2)    s.insert(n); } int findPrimitiveRoot(int n) {    unordered_set<int> s;    if (isPrimeNumber(n)==false)    return -1;    int ETF = n-1;    GeneratePrimes(s, ETF);    for (int r=2; r<=ETF; r++){       bool flag = false;       for (auto it = s.begin(); it != s.end(); it++){          if (power(r, ETF/(*it), n) == 1){             flag = true;             break;          }       }       if (flag == false)       return r;    }    return -1; } int main() {    int n= 13;    cout<<" Smallest primitive root of "<<n<<" is "<<findPrimitiveRoot(n);    return 0; }

Output

Smallest primitive root of 13 is 2