Primitive root modulo n

In modular arithmetic, a branch of number theory, a number g is a primitive root modulo n if every number a coprime to n is congruent to a power of g modulo n. That is, g is a primitive root mod n if for every integer a coprime to n, there is an integer k such that gk ≡ a (mod n). Such a value k is called the index or discrete logarithm of a to the base g modulo n. Note that g is a primitive root mod n if and only if g is a generator of the multiplicative group of integers modulo n.For example, in row 11, 2 is given as the primitive root, and in column 5 the entry is 4. This means that 24 = 16 ≡ 5 (mod 11). For example, in row 11, the index of 6 is the sum of the indices for 2 and 3: 21 + 8 = 512 ≡ 6 (mod 11). The index of 25 is twice the index 5: 28 = 256 ≡ 25 (mod 11). (Of course, since 25 ≡ 3 (mod 11), the entry for 3 is 8).For example, modulo 32 the index for 7 is 2, and 52 = 25 ≡ −7 (mod 32), but the entry for 17 is 4, and 54 = 625 ≡ 17 (mod 32).For example,The Disquisitiones Arithmeticae has been translated from Gauss's Ciceronian Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes. In modular arithmetic, a branch of number theory, a number g is a primitive root modulo n if every number a coprime to n is congruent to a power of g modulo n. That is, g is a primitive root mod n if for every integer a coprime to n, there is an integer k such that gk ≡ a (mod n). Such a value k is called the index or discrete logarithm of a to the base g modulo n. Note that g is a primitive root mod n if and only if g is a generator of the multiplicative group of integers modulo n. Gauss defined primitive roots in Article 57 of the Disquisitiones Arithmeticae (1801), where he credited Euler with coining the term. In Article 56 he stated that Lambert and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist for a prime n. In fact, the Disquisitiones contains two proofs: the one in Article 54 is a nonconstructive existence proof, while the other in Article 55 is constructive. The number 3 is a primitive root modulo 7 because Here we see that the period of 3k modulo 7 is 6. The remainders in the period, which are 3, 2, 6, 4, 5, 1, form a rearrangement of all nonzero remainders modulo 7, implying that 3 is indeed a primitive root modulo 7. This derives from the fact that a sequence (gk modulo n) always repeats after some value of k, since modulo n produces a finite number of values. If g is a primitive root modulo n and n is prime, then the period of repetition is n-1. Curiously, permutations created in this way (and their circular shifts) have been shown to be Costas arrays. If n is a positive integer, the integers between 0 and 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 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 2pk 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 φ(n) (sequence A000010 in the OEIS). 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. For example, if n = 14 then the elements of Zn× are the congruence classes {1, 3, 5, 9, 11, 13}; there are φ(14) = 6 of them. Here is a table of their powers modulo 14: