11.10 RootsUnityMod

RootsUnityMod( m )
RootsUnityMod( k, m )

In the first form RootsUnityMod computes the square roots of 1 modulo the integer m, i.e., the set of all positive integers r less than n such that r^2 = 1 mod m.

In the second form RootsUnityMod computes the kth roots of 1 modulo the integer m, i.e., the set of all positive integers r less than n such that r^k = 1 mod m.

In general there are k^n such roots if the modulus m has n different prime factors p such that p = 1 mod k. If k^2 divides m then there are k^{n+1} such roots; and especially if k = 2 and 8 divides m there are 2^{n+2} such roots.

If you are interested in the full set of roots of another number instead of 1 use RootsUnityMod together with RootMod (see RootMod).

In the current implementation k must be a prime.

RootsUnityMod is efficient even for large values of m, actually most time is usually spent factoring m (see FactorsInt).

    gap> RootsUnityMod(7*31);
    [ 1, 92, 125, 216 ]
    gap> RootsUnityMod(3,7*31);
    [ 1, 25, 32, 36, 67, 149, 156, 191, 211 ]
    gap> RootsUnityMod(5,7*31);
    [ 1, 8, 64, 78, 190 ]
    gap> List( RootMod( 64, 1009 ) * RootsUnityMod( 1009 ),
    >          x -> x mod 1009 );
    [ 1001, 8 ]        # set of all square roots of 64 mod 1009 

Previous Up Top
Index