Non User
Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z	Business Non User Industries Finance Tax

Home > Primitive root modulo n

If n≥1 is an integer, the numbers coprime to n, taken modulo n, form a group with multiplication as operation; it is written as (Z/nZ)^× or Z_n^*. This group is cyclic if and only if n is equal to 1 or 2 or 4 or p^k or 2 p^k for an odd prime number p and k ≥ 1. A generator of this cyclic group is called a primitive root modulo n, or a primitive element of Z_n^*.

A primitive root modulo n, in other words, is an integer g such that, modulo n, every integer not having a common factor with n is congruent to a power of g.

Take for example n = 14. The elements of

(Z/14Z)^×

are the congruence classes of

1, 3, 5, 9, 11 and 13.

Then 3 is a primitive root modulo 14, as we have 3² = 9, 3³ = 13, 3⁴ = 11, 3⁵ = 5 and 3⁶ = 1 (modulo 14). The only other primitive root modulo 14 is 5.

Here is a table containing the smallest primitive root for various values of n (see A046145):

No simple general formula to compute primitive roots modulo n is known. There are however methods to locate a primitive root that are faster than simply trying out all candidates. If the multiplicative order of a number m modulo n is equal to φ(n) (the order of Z/nZ), then it is a primitive root. We can use this to test for primitive roots:

first compute φ(n). Then determine the different prime factors of φ(n), say p₁,...,p_k. Now, for every element m of (Z/nZ)^×, compute

using the fast exponentiating by squaring. As soon as you find a number m for which these k results are all different from 1, you stop: m is a primitive root.

The number of primitive roots modulo n, if there are any, is equal to

φ(φ(n))

since, in general, a cyclic group with r elements has φ(r) generators.

Sometimes one is interested in small primitive roots. We have the following results. For every ε>0 there exist positive constants C and p₀ such that, for every prime p ≥ p₀, there exists a primitive root modulo p that is less than

C p^1/4+ε.

If the generalized Riemann hypothesis is true, then for every prime number p, there exists a primitive root modulo p that is less than

70 ( ln(p))².

See also: Artin conjecture.

Politics	Business	Finance

Topics: Primitive Root Modulo N Number Roots Prime Group Compute Equal...

---

Primitive notionIn mathematics, a primitive notion is something that is not defined in terms of previously defined terms. That is, it is something that is taken to be true as an axiom rather than something that can be proved from a set of further axioms. For example in n Primitive recursive functionIn computability theory, primitive recursive functions are a class of functions which form an important building block on the way to a full formalization of computability. They are defined using recursion and composition as central operations and are a st Primitive LyricsPrimitive Lyrics is a hip hop crew from Switzerland, formed out of the members of Graffiti Crew UC from Zurich. The group was one of the first Swiss dialect hip hop crews. Their first album was 1992's Halbi Nuni Chloricht''. The follow-up was 1996's FLAG' PrimitiveThe word primitive can refer to: primitive art and Primitivism (art) primitive (biology) primitive (computer science) primitive (linguistics) primitive (mathematics) primitive (ontology) Primitive (song). Primitive root modulo nPrimitive roots modulo n are a concept from modular arithmetic, in number theory. If n ge;1 is an integer, the numbers coprime to n taken modulo n form a group with multiplication as operation; it is written as Z ''n Z × or Z . This group is cyclic if and Primitive (song)Primitive a song written and performed by 1980s icon and singer Cyndi Lauper, appeared on her 1989 album A Night to Remember which bombed commercially. However, this song became a Dutch hit single and reached #1 in the Netherlands music charts. Primitive equations Primitive semiperfect number Primitive Baptist Primitive element Primitive type Primitive (album) Primitive Advent Christian Church Primitive root Primitive element (field theory)