As primitive roots are in number theory one branch of mathematics , certain elements of the reduced residue class groups designated. The defining property of a primitive root is that each element of the prime residue class group can be represented as a power of the primitive root.
The number 3 is a primitive root modulo 7, there applies
All elements of the prime remainder class group can be represented modulo 7 as powers of 3, the exponent being the index assigned to the respective element ( discrete logarithm ). The number 2 is not a primitive root modulo 7, there is, so the remainders are repeated in the sequence of powers of 2 modulo 7
after 3 steps each, therefore not all 6 different prime residues modulo 7 are reached and 2 does not generate the prime residue class group .
Definition and conditions of existence
An integer is a primitive root modulo if the residue class generates the prime residue class group . This means that an integer is a primitive root modulo if and only if the order of modulo is equal to the group order of the prime residue class group:
where is the Carmichael function .
applies. It denotes the set of prime numbers.
If there are modulo primitive roots , then there are exactly modulo incongruent primitive roots . Each of these primitive roots is modulo congruent to an element of the set:
where any primitive root is modulo .
Calculation of primitive roots
Trying out (brute force)
To determine whether a number is primitive root modulo , first and then the order of is calculated. The order can be determined, for example, by successively calculating the values for . The first thing to be true is the order of .
In the example from the introduction you can see that the 3 has the order 6. Since, in addition , 3 is a primitive root modulo 7.
A number that is not a primitive root modulo 7 is 4. Here applies
The order of 4 is therefore 3 and 4 is not a primitive root modulo 7.
One can save many trials by using the fact that the order divides according to Lagrange's theorem , since every number for which holds is divisible by the order. Therefore, one only has to check for all factors of whether exponentiation with them maps the number to 1, and the smallest such factor is the order.
Primitive roots modulo prime numbers
The prime residue class groups for modules that are prime numbers consist of exactly elements. The numbers are the representatives of the different remainder classes. If a primitive root is modulo , the expression assumes for all values (in apparently random order).
The following table shows the primitive roots modulo of the prime numbers up to 29.
|Primitive roots modulo|
|11||4th||2, 6, 7, 8|
|13||4th||2, 6, 7, 11|
|17th||8th||3, 5, 6, 7, 10, 11, 12, 14|
|19th||6th||2, 3, 10, 13, 14, 15|
|23||10||5, 7, 10, 11, 14, 15, 17, 19, 20, 21|
|29||12||2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27|
Primitive roots modulo prime powers
If an odd prime number, then a primitive root is modulo with also primitive root modulo smaller powers of . What is interesting for the search for primitive roots modulo higher powers of is that a primitive root is modulo (with ) also a primitive root to all higher powers of . Therefore, for higher powers of the prime number , it is sufficient
- to find a primitive root modulo (among the numbers ),
- to test the numbers to see if they are primitive roots modulo . What is necessary and already sufficient for this is that it is. In fact, this already occurs for or , i.e. H. or is a primitive root modulo .
Then with every number determined in the second step one has a primitive root modulo for any number .
If the primitive root determined in this way is odd, then it is also primitive root modulo , otherwise this applies to .
- it is easy to a given prime , primitive root and integer one calculate with ,
- It is laborious to find a corresponding one (the so-called discrete logarithm ) for a known one .
- Carl Friedrich Gauß : Investigations into higher arithmetic (German translation), Original: Leipzig 1801.
- Peter Bundschuh : Introduction to Number Theory . 5th edition. Springer Verlag, 2002, ISBN 3-540-43579-4 , pp. 109-120
- Armin Leutbecher: Number Theory - An Introduction to Algebra . 1st edition. Springer Verlag, 1996, Berlin Heidelberg New York. ISBN 3-540-58791-8 .
The latter is generally closer to the element order, because it applies to everyone
- A. Leutbecher: Number Theory - An Introduction to Algebra. Pp. 53-54.
- Carl Friedrich Gauss: Investigations on higher arithmetic. H. Maser, 1889, p. Art. 92 , accessed January 30, 2017 .