isPrimitiveRoot

Determine which array elements are primitive roots

Syntax

TF = isPrimitiveRoot(G,N)

Description

TF = isPrimitiveRoot(G,N) returns a logical array containing 1 (true) for the corresponding elements of G that are primitive roots modulo N, and 0 (false) for the corresponding elements that are not primitive roots. The elements of G must be integers, and the elements of N must be positive integers.

Examples

Find Primitive Roots Modulo 11

Create a row vector containing positive integers from 1 to 11. Determine if they are primitive roots modulo 11.

G = 1:11;
TF = isPrimitiveRoot(G,11)

TF = 1x11 logical array

   0   1   0   0   0   1   1   1   0   0   0

Find the smallest positive integer that is a primitive root modulo 11.

Z1 = find(TF,1)

Z1 = 2

Show all positive integers (less than or equal to 11) that are primitive roots modulo 11.

Z = G(TF)

Z = 1×4

     2     6     7     8

Find Primitive Roots Modulo 15

Create a row vector containing integers from –15 to 15. Find the integers that are primitive roots modulo 15.

G = -15:15;
Z = G(isPrimitiveRoot(G,15))

Z =

  1x0 empty double row vector

The integer 15 has no primitive roots.

Input Arguments

G — Base

number | vector | matrix | array | symbolic number | symbolic array

Base, specified as a number, vector, matrix, array, symbolic number, or symbolic array. The elements of G must be integers. G and N must be the same size, or else one of them must be a scalar.

Data Types: single | double | sym

N — Divisor

number | vector | matrix | array | symbolic number | symbolic array

Divisor, specified as a number, vector, matrix, array, symbolic number, or symbolic array. The elements of N must be positive integers. G and N must be the same size, or else one of them must be a scalar.

Data Types: single | double | sym

More About

Primitive Root

A number g is a primitive root modulo n if every number a coprime to n (or $$\gcd (a,n)=1$$) is congruent to a power of g modulo n. That is, g is a primitive root modulo n if for every integer a coprime to n, there is an integer k such that $$g^k\equiv a(\text{mod }n)$$. The primitive roots modulo n exist if and only if $$n=1,2,4,p^k,\text{or }2p^k$$, where p is an odd prime and k is a positive integer.

For example, the integer 2 is a primitive root modulo 5 because $$2^k\equiv a(\text{mod 5})$$ is satisfied for every integer a that is coprime to 5.

$$\begin{array}{l}{2}^1=2\equiv 2(\text{mod 5})\\ 2^2=4\equiv 4(\text{mod 5})\\ 2^3=8\equiv 3(\text{mod 5})\\ 2^4=16\equiv 1(\text{mod 5})\\ ⋮\end{array}$$