|
Each of the functions in this section may take an integer or the
factorization of that integer.
CarmichaelLambda(Q) : RngIntEltFact -> RngIntElt
CarmichaelLambda(Q) : [Tup] -> RngIntElt
The Carmichael function λ(n); its value equals
the exponent of (Z/nZ)^*.
Computes ρ(u) where ρ is Dickman's rho function.
FactoredCarmichaelLambda(Q) : RngIntEltFact -> RngIntEltFact
FactoredCarmichaelLambda(Q) : [Tup] -> RngIntEltFact
The Carmichael function λ(n), returned as a factorization sequence.
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(Q) : RngIntEltFact -> RngIntElt
The number of divisors of the positive integer n. This is a special
case of DivisorSigma.
SumOfDivisors(Q) : RngIntEltFact -> RngIntElt
The sum of the divisors of the positive integer n. This is a special
case of DivisorSigma.
EulerPhi(Q) : RngIntEltFact -> RngIntElt
EulerPhi(Q) : [Tup] -> RngIntElt
The Euler totient function φ(n); its value equals the order
of (Z/nZ)^*.
FactoredEulerPhi(Q) : RngIntEltFact -> RngIntEltFact
FactoredEulerPhi(Q) : [Tup] -> RngIntEltFact
The Euler totient function φ(n), returned as a factorization sequence.
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(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.
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.
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.
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(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.
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
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|