Arithmetic Functions

Each of the functions in this section may take an integer or the factorization of that integer.

CarmichaelLambda(n) : RngIntElt -> RngIntElt
CarmichaelLambda(Q) : RngIntEltFact -> RngIntElt
CarmichaelLambda(Q) : [Tup] -> RngIntElt
The Carmichael function λ(n); its value equals the exponent of (Z/nZ)^*.
DickmanRho(u) : FldReElt -> FldReElt
Computes ρ(u) where ρ is Dickman's rho function.
FactoredCarmichaelLambda(n) : RngIntElt -> RngIntEltFact
FactoredCarmichaelLambda(Q) : RngIntEltFact -> RngIntEltFact
FactoredCarmichaelLambda(Q) : [Tup] -> RngIntEltFact
The Carmichael function λ(n), returned as a factorization sequence.
DivisorSigma(i, n) : RngIntElt, RngIntElt -> RngIntElt
DivisorSigma(i, Q) : RngIntElt, RngIntEltFact -> RngIntElt
The divisor function σi(n), which equals the sum of all the di for d dividing n, for integer n and small non-negative integer i.
NumberOfDivisors(n) : RngIntElt -> RngIntElt
NumberOfDivisors(Q) : RngIntEltFact -> RngIntElt
The number of divisors of the positive integer n. This is a special case of DivisorSigma.
SumOfDivisors(n) : RngIntElt -> RngIntElt
SumOfDivisors(Q) : RngIntEltFact -> RngIntElt
The sum of the divisors of the positive integer n. This is a special case of DivisorSigma.
EulerPhi(n) : RngIntElt -> RngIntElt
EulerPhi(Q) : RngIntEltFact -> RngIntElt
EulerPhi(Q) : [Tup] -> RngIntElt
The Euler totient function φ(n); its value equals the order of (Z/nZ)^*.
FactoredEulerPhi(n) : RngIntElt -> RngIntEltFact
FactoredEulerPhi(Q) : RngIntEltFact -> RngIntEltFact
FactoredEulerPhi(Q) : [Tup] -> RngIntEltFact
The Euler totient function φ(n), returned as a factorization sequence.
EulerPhiInverse(m) : RngIntElt -> RngIntElt
EulerPhiInverse(Q) : RngIntEltFact -> RngIntElt
The inverse of the Euler totient function φ(n); that is, the sorted sequence of all integers n such that φ(n)=m.
FactoredEulerPhiInverse(n) : RngIntElt -> RngIntEltFact
FactoredEulerPhiInverse(Q) : RngIntEltFact -> RngIntEltFact
The factored inverse of the Euler totient function φ(n); that is, the sorted sequence of the factorizations of all integers n such that φ(n)=m.
LegendreSymbol(n, m) : RngIntElt, RngIntElt -> RngIntElt
The Legendre symbol ((n/m)): for prime m this checks whether or not n is a quadratic residue modulo m. The function returns 0 if m divides n, -1 if n is not a quadratic residue, and 1 if n is a quadratic residue modulo m. A fast probabilistic primality test is performed on m. If m fails the test (and is therefore composite), an error results; if it passes the test the Jacobi symbol is computed.
JacobiSymbol(n, m) : RngIntElt, RngIntElt -> RngIntElt
The Jacobi symbol ((n/m)). For odd m > 1 this is defined (but not calculated!) as the product of the Legendre symbols ((n/pi)), where the product is taken over all primes pi dividing m including multiplicities. Quadratic reciprocity is used to calculate this symbol, which has the values -1, 0 or 1.
KroneckerSymbol(n, m) : RngIntElt, RngIntElt -> RngIntElt
The Kronecker symbol ((n/m)). This is the extension of the Jacobi symbol to all integers m, by multiplicativity, and by defining ((n/2))=( - 1)(n2 - 1)/8 for odd n (and 0 for even n) and ((n/- 1)) equals plus or minus 1 according to the sign of n for n != 0 (and 1 for n = 0).
MoebiusMu(n) : RngIntElt -> RngIntElt
MoebiusMu(Q) : RngIntEltFact -> RngIntElt
The Möbius function μ(n). This is a multiplicative function characterized by μ(1)=1, μ(p)= - 1, and μ(pk)=0 for k ≥2, where p is a prime number.

Example RngInt_Amicable (H19E5)

A pair of positive integers (m, n) is called amicable if the sum of the proper divisors (that is: excluding m itself) of m equals n, and vice versa. The following function finds such pairs. Note that it also finds perfect numbers: amicable pairs of the form (m, m). 
> d := func< m | DivisorSigma(1, m)-m >;
> z := func< m | d(d(m)) eq m >;
> for m := 2 to 10000 do
>     if z(m) then
>         m, d(m);
>     end if;
> end for;
6 6
28 28
220 284
284 220
496 496
1184 1210
1210 1184
2620 2924
2924 2620
5020 5564
5564 5020
6232 6368
6368 6232
8128 8128
V2.28, 13 July 2023