11.4 OrderMod

OrderMod( n, m )

OrderMod returns the multiplicative order of the integer n modulo the positive integer m. If n is less than 0 or larger than m it is replaced by its remainder. If n and m are not relatively prime the order of n is not defined and OrderMod will return 0.

If n and m are relatively prime the multiplicative order of n modulo m is the smallest positive integer i such that n^i = 1 mod m. Elements of maximal order are called primitive roots (see Phi).

OrderMod usually spends most of its time factoring m and phi(m) (see FactorsInt).

    gap> OrderMod( 2, 7 );
    3
    gap> OrderMod( 3, 7 );
    6        # 3 is a primitive root modulo 7 

Previous Up Top Next
Index