Definition
If n is a positive integer, the integers between 1 and n−1 which 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 Zn× 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 group is cyclic if and only if n is equal to 2, 4, pk, or 2 pk where pk is a power of an odd prime number. A generator of this cyclic group is called a primitive root modulo n, or a primitive element of Zn×.
The order of (i.e. the number of elements in) Zn× is given by Euler's totient function Euler's theorem says that aφ(n) ≡ 1 (mod n) for every a coprime to n; the lowest power of a which is congruent to 1 modulo n is called the multiplicative order of a modulo n. In particular, for a to be a primitive root modulo n, φ(n) has to be the smallest power of a which is congruent to 1 modulo n.
Read more about this topic: Primitive Root Modulo n
Famous quotes containing the word definition:
“The man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.”
—William James (1842–1910)
“No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
—Florence Nightingale (1820–1910)
“Scientific method is the way to truth, but it affords, even in
principle, no unique definition of truth. Any so-called pragmatic
definition of truth is doomed to failure equally.”
—Willard Van Orman Quine (b. 1908)