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"`

.

- PrimeResidues
- Phi
- Lambda
- OrderMod
- IsPrimitiveRootMod
- PrimitiveRootMod
- Jacobi
- Legendre
- RootMod
- RootsUnityMod

`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 *2 ^{28}*, 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 *p ^{e}*, or twice an odd prime
power

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

`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 = p _{1}^{e1} p_{2}^{e2} ... p_{k}^{ek}*. Then

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 *p ^{e}*, or twice an odd prime power

`Phi`

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

gap> Phi( 12 ); 4 gap> Phi( 2^13-1 ); 8190 # which proves that2is a prime gap> Phi( 2^15-1 ); 27000^{13}-1

`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 *a ^{l}=1* mod

Carmichael's theorem states that *λ* can be computed as follows
*λ(2)=1*, *λ(4)=2* and *λ(2 ^{e}) = 2^{e-2}* if

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 *10 ^{10}* 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 *p ^{e}*, or twice an odd prime power

`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

`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

`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

`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 *p ^{e}*, or twice an odd prime
power

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

`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 *p ^{e}*, or twice an odd prime
power

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

`Jacobi( `

`n`, `m` )

`Jacobi`

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

Suppose that *m = p _{1} p_{2} .. p_{k}* as a product of primes, not necessarily
distinct. Then for

If *n* is an **quadratic residue** modulo *m*, i.e., if there exists an *r*
such that *r ^{2} = n* mod

`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 #9mod^{2}= 1135gap> Jacobi( 6, 35 ); -1 # thus there is norsuch thatrmod^{2}= 635gap> Jacobi( 3, 35 ); 1 # even though there is norwithrmod^{2}= 335

`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 *r ^{2}
= n* mod

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 #4mod^{2}= 511gap> Legendre( 6, 11 ); -1 # thus there is norsuch thatrmod^{2}= 611gap> Legendre( 3, 35 ); -1 # thus there is norsuch thatrmod^{2}= 335

`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 *r ^{2} = n*
mod

`RootMod`

returns `false`

.
A root of `n` exists only if `Legendre(`

(see Legendre).
If `n`,`m`) = 1`m` has `k` different prime factors then there are *2 ^{k}* different
roots of

`RootMod`

returns.
You can, however, use `RootsUnityMod`

(see RootsUnityMod) to compute
the full set of roots.
In the second form `RootMod`

computes a `k`th root of the integer `n`
modulo the positive integer `m`, i.e., an integer `r` such that *r ^{k} = n*
mod

`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

`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

In the second form `RootsUnityMod`

computes the `k`th 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

In general there are *k ^{n}* such roots if the modulus

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

gap3-jm

11 Mar 2019