Wednesday, 10 December 2014

elementary number theory - Checking understanding of Order, Primitive Roots



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 5a1(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 5a1(18).



Since the powers of 5 modulo 18 are:
515,   527,   5317,   5413,  5511,   561,
the order of 5 modulo 18 is 6.




We need to be very careful when stating this definition. It's true that 5121(18) and 5181(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

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...