https://en.wikipedia.org/wiki/Primitive_root_modulo_n Primitive root modulo n Definition If n is a positive integer, the integers from 0 to n - 1 that are coprime to n (or equivalently, the congruence classes coprime to n) form a group, with multiplication modulo n as the operation; it is denoted by Z^×n, and is called the group of units modulo n, or the group of primitive classes modulo n. As explained in the article multiplicative group of integers modulo n, this multiplicative group (Z^×n) is cyclic if and only if n is equal to 2, 4, p^k, or 2p^k where p^k is a power of an odd prime number.[2][3][4]
When (and only when) this group Z^×n is cyclic, a generator of this cyclic group is called a primitive root modulo n[5] (or in fuller language primitive root of unity modulo n, emphasizing its role as a fundamental solution of the roots of unity polynomial equations X^m - 1 in the ring Zn), or simply a primitive element of Z^×n. When Z^×n is non-cyclic, such primitive elements mod n do not exist. Instead, each prime component of n has its own sub-primitive roots (see 15 in the examples below). (引用終り) 以上
