Search code examples
mathcryptographylinear-algebradiscrete-mathematicsnumber-theory

Multiplicative orders Vs order of a multiplicative group

How to demonstrate that all multiplicative orders divide the order (size) of the multiplicative group F of F13. .

Solution

  • You show that the cyclic group <x> generated by an element x is a subgroup of IF* and that "u~v iff u^(-1)*v in <x>" is an equivalence relation that divides the multiplicative group into equivalence classes of equal size.

    So that you get 

    [size of IF*] 
     = [size of <x>] * [number of equivalence classes]

    which means that the order of x = [size of <x>] is a divisor of the number of invertible elements, i.e., the size of the multiplicative group of IF

    See also the little theorem of Fermat.