Primitve Roots of Prime Numbers

A number \(\alpha\) is a primitive root \(\bmod n\) if every number coprime to \(n\) is congruent to a power of \(\alpha \bmod n\)

We can say that \(\alpha\) is said to be a primitive root of prime number \(p\) if the following are distinct:

\[\alpha^{1} \bmod p, \alpha^{2} \bmod p, \cdots, \alpha^{p-1}\bmod p\]

Example

• \(2\) is a primitive root of prime number \(5\)

\[\displaylines{ \begin{array}{|c|c|c|c|} \hline 2^1 \bmod 5 & 2 \bmod 5 & 2 \\ \hline 2^2 \bmod 5 & 4 \bmod 5 & 4 \\ \hline 2^3 \bmod 5 & 8 \bmod 5 & 3 \\ \hline 2^4 \bmod 5 & 16 \bmod 5 & 1 \\ \hline \end{array} }\]

• \(3\) is a primitive root of prime number \(7\)

\[\displaylines{ \begin{array}{|c|c|c|c|} \hline 3^1 \bmod 7 & 3 \bmod 7 & 3 \\ \hline 3^2 \bmod 7 & 9 \bmod 7 & 2 \\ \hline 3^3 \bmod 7 & 27 \bmod 7 & 6 \\ \hline 3^4 \bmod 7 & 81 \bmod 7 & 4 \\ \hline 3^5 \bmod 7 & 243 \bmod 7 & 5 \\ \hline 3^6 \bmod 7 & 729 \bmod 7 & 1 \\ \hline \end{array} }\]

• \(2\) is not a primitve root of prime number \(7\)

\[\displaylines{ \begin{array}{|c|c|c|c|} \hline 2^1 \bmod 7 & 2 \bmod 7 & 2 \\ \hline 2^2 \bmod 7 & 4 \bmod 7 & 4 \\ \hline 2^3 \bmod 7 & 8 \bmod 7 & 1 \\ \hline 2^4 \bmod 7 & 16 \bmod 7 & \color{red}2 \\ \hline 2^5 \bmod 7 & 32 \bmod 7 & \color{red}4 \\ \hline 2^6 \bmod 7 & 64 \bmod 7 & \color{red}1 \\ \hline \end{array} }\]

• Sample Ruby Code

  def proot?(n, p)
    items = []
    (1..(p - 1)).to_a.each do |e|
      a = n ** e
      b = a % p
      items << {number: a, calc: b}
    end
    total = items.collect {|x| x[:calc] }
    is_root = total.count == total.uniq.count
    data = {result:  is_root, items: items }
    return data
  end
  

---