11 Number Theory

The integers relatively prime to m form a group under multiplication modulo m, called the prime residue group. This chapter describes the functions that deal with this group.

The first section describes the function that computes the set of representatives of the group (see PrimeResidues).

The next sections describe the functions that compute the size and the exponent of the group (see Phi and Lambda).

The next section describes the function that computes the order of an element in the group (see OrderMod).

The next section describes the functions that test whether a residue generates the group or computes a generator of the group, provided it is cyclic (see IsPrimitiveRootMod, PrimitiveRootMod).

The next section describes the functions that test whether an element is a square in the group (see Jacobi and Legendre).

The next sections describe the functions that compute general roots in the group (see RootMod and RootsUnityMod).

All these functions are in the file LIBNAME/"numtheor.g".

Subsections

  1. PrimeResidues
  2. Phi
  3. Lambda
  4. OrderMod
  5. IsPrimitiveRootMod
  6. PrimitiveRootMod
  7. Jacobi
  8. Legendre
  9. RootMod
  10. RootsUnityMod

11.1 PrimeResidues

PrimeResidues( m )

PrimeResidues returns the set of integers from the range 0..Abs(m)-1 that are relatively prime to the integer m.

Abs(m) must be less than 228, otherwise the set would probably be too large anyhow.

The integers relatively prime to m form a group under multiplication modulo m, called the prime residue group. φ(m) (see Phi) is the order of this group, λ(m) (see Lambda) the exponent. If and only if m is 2, 4, an odd prime power pe, or twice an odd prime power 2 pe, this group is cyclic. In this case the generators of the group, i.e., elements of order φ(m), are called primitive roots (see IsPrimitiveRootMod, PrimitiveRootMod).

    gap> PrimeResidues( 0 );
    [  ]
    gap> PrimeResidues( 1 );
    [ 0 ]
    gap> PrimeResidues( 20 );
    [ 1, 3, 7, 9, 11, 13, 17, 19 ] 

11.2 Phi

Phi( m )

Phi returns the value of the Euler totient function φ(m) for the integer m. φ(m) is defined as the number of positive integers less than or equal to m that are relatively prime to m.

Suppose that m = p1e1 p2e2 ... pkek. Then φ(m) is p1e1-1 (p1-1) p2e2-1 (p2-1) ... pkek-1 (pk-1). It follows that m is a prime if and only if φ(m) = m - 1.

The integers relatively prime to m form a group under multiplication modulo m, called the prime residue group. It can be computed with PrimeResidues (see PrimeResidues). φ(m) is the order of this group, λ(m) (see Lambda) the exponent. If and only if m is 2, 4, an odd prime power pe, or twice an odd prime power 2 pe, this group is cyclic. In this case the generators of the group, i.e., elements of order φ(m), are called primitive roots (see IsPrimitiveRootMod, PrimitiveRootMod).

Phi usually spends most of its time factoring m (see FactorsInt).

    gap> Phi( 12 );
    4
    gap> Phi( 2^13-1 );
    8190        # which proves that 213-1 is a prime
    gap> Phi( 2^15-1 );
    27000 

11.3 Lambda

Lambda( m )

Lambda returns the exponent of the group of relatively prime residues modulo the integer m.

λ(m) is the smallest positive integer l such that for every a relatively prime to m we have al=1 mod m. Fermat's theorem asserts aφ(m)=1 mod m, thus λ(m) divides φ(m) (see Phi).

Carmichael's theorem states that λ can be computed as follows λ(2)=1, λ(4)=2 and λ(2e) = 2e-2 if 3 <= e, λ(pe) = (p-1) pe-1 (= φ(pe)) if p is an odd prime, and λ(n m) = Lcm(λ(n),λ(m)) if n, m are relatively prime.

Composites for which λ(m) divides m - 1 are called Carmichaels. If 6k+1, 12k+1 and 18k+1 are primes their product is such a number. It is believed but unproven that there are infinitely many Carmichaels. There are only 1547 Carmichaels below 1010 but 455052511 primes.

The integers relatively prime to m form a group under multiplication modulo m, called the prime residue group. It can be computed with PrimeResidues (see PrimeResidues). φ(m) (see Phi) is the order of this group, λ(m) the exponent. If and only if m is 2, 4, an odd prime power pe, or twice an odd prime power 2 pe, this group is cyclic. In this case the generators of the group, i.e., elements of order φ(m), are called primitive roots (see IsPrimitiveRootMod, PrimitiveRootMod).

Lambda usually spends most of its time factoring m (see FactorsInt).

    gap> Lambda( 10 );
    4
    gap> Lambda( 30 );
    4
    gap> Lambda( 561 );
    80        # 561 is the smallest Carmichael number 

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 ni = 1 mod m. Elements of maximal order are called primitive roots (see Phi).

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

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

11.5 IsPrimitiveRootMod

IsPrimitiveRootMod( r, m )

IsPrimitiveRootMod returns true if the integer r is a primitive root modulo the positive integer m and false otherwise. If r is less than 0 or larger than m it is replaced by its remainder.

The integers relatively prime to m form a group under multiplication modulo m, called the prime residue group. It can be computed with PrimeResidues (see PrimeResidues). φ(m) (see Phi) is the order of this group, λ(m) (see Lambda) the exponent. If and only if m is 2, 4, an odd prime power pe, or twice an odd prime power 2 pe, this group is cyclic. In this case the generators of the group, i.e., elements of order φ(m), are called primitive roots (see also PrimitiveRootMod).

    gap> IsPrimitiveRootMod( 2, 541 );
    true
    gap> IsPrimitiveRootMod( -539, 541 );
    true        # same computation as above
    gap> IsPrimitiveRootMod( 4, 541 );
    false
    gap> ForAny( [1..29], r -> IsPrimitiveRootMod( r, 30 ) );
    false        # there does not exist a primitive root modulo 30 

11.6 PrimitiveRootMod

PrimitiveRootMod( m )
PrimitiveRootMod( m, start )

PrimitiveRootMod returns the smallest primitive root modulo the positive integer m and false if no such primitive root exists. If the optional second integer argument start is given PrimitiveRootMod returns the smallest primitive root that is strictly larger than start.

The integers relatively prime to m form a group under multiplication modulo m, called the prime residue group. It can be computed with PrimeResidues (see PrimeResidues). φ(m) (see Phi) is the order of this group, λ(m) (see Lambda) the exponent. If and only if m is 2, 4, an odd prime power pe, or twice an odd prime power 2 pe, this group is cyclic. In this case the generators of the group, i.e., elements of order φ(m), are called primitive roots (see also IsPrimitiveRootMod).

    gap> PrimitiveRootMod( 409 );
    21        # largest primitive root for a prime less than 2000
    gap> PrimitiveRootMod( 541, 2 );
    10
    gap> PrimitiveRootMod( 337, 327 );
    false        # 327 is the largest primitive root mod 337
    gap> PrimitiveRootMod( 30 );
    false        # the exists no primitive root modulo 30 

11.7 Jacobi

Jacobi( n, m )

Jacobi returns the value of the Jacobi symbol of the integer n modulo the integer m.

Suppose that m = p1 p2 .. pk as a product of primes, not necessarily distinct. Then for n relatively prime to m the Jacobi symbol is defined by J(n/m) = L(n/p1) L(n/p2) .. L(n/pk), where L(n/p) is the Legendre symbol (see Legendre). By convention J(n/1) = 1. If the gcd of n and m is larger than 1 we define J(n/m) = 0.

If n is an quadratic residue modulo m, i.e., if there exists an r such that r2 = n mod m then J(n/m) = 1. However J(n/m) = 1 implies the existence of such an r only if m is a prime.

Jacobi is very efficient, even for large values of n and m, it is about as fast as the Euclidean algorithm (see Gcd).

    gap> Jacobi( 11, 35 );
    1         # 92 = 11 mod 35
    gap> Jacobi( 6, 35 );
    -1        # thus there is no r such that r2 = 6 mod 35
    gap> Jacobi( 3, 35 );
    1         # even though there is no r with r2 = 3 mod 35 

11.8 Legendre

Legendre( n, m )

Legendre returns the value of the Legendre symbol of the integer n modulo the positive integer m.

The value of the Legendre symbol L(n/m) is 1 if n is a quadratic residue modulo m, i.e., if there exists an integer r such that r2 = n mod m and -1 otherwise.

If a root of n exists it can be found by RootMod (see RootMod).

While the value of the Legendre symbol usually is only defined for m a prime, we have extended the definition to include composite moduli too. The Jacobi symbol (see Jacobi) is another generalization of the Legendre symbol for composite moduli that is much cheaper to compute, because it does not need the factorization of m (see FactorsInt).

    gap> Legendre( 5, 11 );
    1         # 42 = 5 mod 11
    gap> Legendre( 6, 11 );
    -1        # thus there is no r such that r2 = 6 mod 11
    gap> Legendre( 3, 35 );
    -1        # thus there is no r such that r2 = 3 mod 35 

11.9 RootMod

RootMod( n, m )
RootMod( n, k, m )

In the first form RootMod computes a square root of the integer n modulo the positive integer m, i.e., an integer r such that r2 = n mod m. If no such root exists RootMod returns false.

A root of n exists only if Legendre(n,m) = 1 (see Legendre). If m has k different prime factors then there are 2k different roots of n mod m. It is unspecified which one RootMod returns. You can, however, use RootsUnityMod (see RootsUnityMod) to compute the full set of roots.

In the second form RootMod computes a kth root of the integer n modulo the positive integer m, i.e., an integer r such that rk = n mod m. If no such root exists RootMod returns false.

In the current implementation k must be a prime.

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

    gap> RootMod( 64, 1009 );
    1001        # note RootMod does not return 8 in this case but -8
    gap> RootMod( 64, 3, 1009 );
    518
    gap> RootMod( 64, 5, 1009 );
    656
    gap> List( RootMod( 64, 1009 ) * RootsUnityMod( 1009 ),
    >          x -> x mod 1009 );
    [ 1001, 8 ]        # set of all square roots of 64 mod 1009 

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 r2 = 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 rk = 1 mod m.

In general there are kn such roots if the modulus m has n different prime factors p such that p = 1 mod k. If k2 divides m then there are kn+1 such roots; and especially if k = 2 and 8 divides m there are 2n+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 Next
Index

gap3-jm
08 Sep 2017