# 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 $\lambda(n)$; its value equals the exponent of ${({{\mathbb{Z}}/n{\mathbb{Z}}})^*}$.

## `DickmanRho(u): FldReElt -> FldReElt`

Computes $\rho(u)$ where $\rho$ is Dickman’s rho function.

## `FactoredCarmichaelLambda(n): RngIntElt -> RngIntEltFact`

## `FactoredCarmichaelLambda(Q): RngIntEltFact -> RngIntEltFact`

## `FactoredCarmichaelLambda(Q): [Tup] -> RngIntEltFact`

The Carmichael function $\lambda(n)$, returned as a factorization sequence.

## `DivisorSigma(i, n): RngIntElt, RngIntElt -> RngIntElt`

## `DivisorSigma(i, Q): RngIntElt, RngIntEltFact -> RngIntElt`

The divisor function $\sigma_i(n)=\sum_{d\vert n}d^i$ 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 $\phi(n)$; its value equals the order of ${({{\mathbb{Z}}/n{\mathbb{Z}}})^*}$.

## `FactoredEulerPhi(n): RngIntElt -> RngIntEltFact`

## `FactoredEulerPhi(Q): RngIntEltFact -> RngIntEltFact`

## `FactoredEulerPhi(Q): [Tup] -> RngIntEltFact`

The Euler totient function $\phi(n)$, returned as a factorization sequence.

## `EulerPhiInverse(m): RngIntElt -> RngIntElt`

## `EulerPhiInverse(Q): RngIntEltFact -> RngIntElt`

The inverse of the Euler totient function $\phi(n)$; that is, the sorted sequence of all integers $n$ such that $\phi(n)=m$.

## `FactoredEulerPhiInverse(n): RngIntElt -> RngIntEltFact`

## `FactoredEulerPhiInverse(Q): RngIntEltFact -> RngIntEltFact`

The factored inverse of the Euler totient function $\phi(n)$; that is, the sorted sequence of the factorizations of all integers $n$ such that $\phi(n)=m$.

## `LegendreSymbol(n, m): RngIntElt, RngIntElt -> RngIntElt`

The Legendre symbol $\left({n\over m}\right)$: 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 $\left({n\over m}\right)$. For odd $m > 1$ this is defined (but not calculated!) as the product of the Legendre symbols $\left({n\over p_i}\right)$, where the product is taken over all primes $p_i$ 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 $\left({n\over m}\right)$. This is the extension of the Jacobi symbol to all integers $m$, by multiplicativity, and by defining $\left({n\over 2}\right)=(-1)^{(n^2-1)/8}$ for odd $n$ (and $0$ for even $n$) and $\left({n\over -1}\right)=\pm1$ according to the sign of $n$ for $n\neq 0$ (and $1$ for $n = 0$).

## `MoebiusMu(n): RngIntElt -> RngIntElt`

## `MoebiusMu(Q): RngIntEltFact -> RngIntElt`

The Möbius function $\mu(n)$. This is a multiplicative function characterized by $\mu(1)=1$, $\mu(p)=-1$, and $\mu(p^k)=0$ for $k \geq 2$, where $p$ is a prime number.

## `Example: Amicable (ex-233f46)`

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)$.

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

```