I dont seem to understand how primitive roots work. I've outlined what I think, if anyone can tell me what I'm misunderstanding I'd really appreciate it!
To calculate the order of 5 modulo 18, our objective is to figure out a when 5a≡1(18) right?
Then the definition of a primitive root is a number a such that
aφ(18)≡1(18) correct?
Answer
The order of 5 modulo 18 is the smallest positive value of a such that 5a≡1(18).
Since the powers of 5 modulo 18 are:
51≡5, 52≡7, 53≡17, 54≡13, 55≡11, 56≡1,
the order of 5 modulo 18 is 6.
We need to be very careful when stating this definition. It's true that 512≡1(18) and 518≡1(18) etc, but it would be incorrect to say that the order of 5 modulo 18 is 12 or 18 etc.
A primitive root modulo 18 is an element of the group of units modulo 18 whose order is equal to φ(18). In other words, a primitive root modulo 18 is an element that generates the group of units.
Since φ(18)=6, and since the order of 5 is 6, it is true that 5 is a primitive root modulo 18.
Again, we need to be very careful when we state the definition. We can't say that a primitive root is any x in the group of units such that xφ(18)≡1(18), because, in fact, every x in the group of units obeys the property xφ(18)≡1(18), by Lagrange's theorem!
Instead, x is a primitive root modulo 18 iff φ(18) is the smallest power of x that is equal to 1 modulo 18.
No comments:
Post a Comment