---
title: "Arithmetic Functions"
canonical: "https://docs.magma-maths.org/v2.30-1/BasicRings/Integers/arithmetic-function.html"
source: "https://docs.magma-maths.org/v2.30-1/BasicRings/Integers/arithmetic-function.md"
part: "Basic Rings"
chapter: "Ring of Integers"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Basic Rings", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/index-basic-rings.md"}
  - {"title": "Ring of Integers", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/Integers/index-integers.md"}
prev: {"title": "GCD and LCM", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/Integers/gcd-lcm.md"}
next: {"title": "Combinatorial Functions", "source": "https://docs.magma-maths.org/v2.30-1/BasicRings/Integers/combinatorics.md"}
intrinsics:
  - {"name": "CarmichaelLambda", "signature": "CarmichaelLambda(n): RngIntElt -> RngIntElt"}
  - {"name": "CarmichaelLambda", "signature": "CarmichaelLambda(Q): RngIntEltFact -> RngIntElt"}
  - {"name": "CarmichaelLambda", "signature": "CarmichaelLambda(Q): [Tup] -> RngIntElt"}
  - {"name": "DickmanRho", "signature": "DickmanRho(u): FldReElt -> FldReElt"}
  - {"name": "FactoredCarmichaelLambda", "signature": "FactoredCarmichaelLambda(n): RngIntElt -> RngIntEltFact"}
  - {"name": "FactoredCarmichaelLambda", "signature": "FactoredCarmichaelLambda(Q): RngIntEltFact -> RngIntEltFact"}
  - {"name": "FactoredCarmichaelLambda", "signature": "FactoredCarmichaelLambda(Q): [Tup] -> RngIntEltFact"}
  - {"name": "DivisorSigma", "signature": "DivisorSigma(i, n): RngIntElt, RngIntElt -> RngIntElt"}
  - {"name": "DivisorSigma", "signature": "DivisorSigma(i, Q): RngIntElt, RngIntEltFact -> RngIntElt"}
  - {"name": "NumberOfDivisors", "signature": "NumberOfDivisors(n): RngIntElt -> RngIntElt"}
  - {"name": "NumberOfDivisors", "signature": "NumberOfDivisors(Q): RngIntEltFact -> RngIntElt"}
  - {"name": "SumOfDivisors", "signature": "SumOfDivisors(n): RngIntElt -> RngIntElt"}
  - {"name": "SumOfDivisors", "signature": "SumOfDivisors(Q): RngIntEltFact -> RngIntElt"}
  - {"name": "EulerPhi", "signature": "EulerPhi(n): RngIntElt -> RngIntElt"}
  - {"name": "EulerPhi", "signature": "EulerPhi(Q): RngIntEltFact -> RngIntElt"}
  - {"name": "EulerPhi", "signature": "EulerPhi(Q): [Tup] -> RngIntElt"}
  - {"name": "FactoredEulerPhi", "signature": "FactoredEulerPhi(n): RngIntElt -> RngIntEltFact"}
  - {"name": "FactoredEulerPhi", "signature": "FactoredEulerPhi(Q): RngIntEltFact -> RngIntEltFact"}
  - {"name": "FactoredEulerPhi", "signature": "FactoredEulerPhi(Q): [Tup] -> RngIntEltFact"}
  - {"name": "EulerPhiInverse", "signature": "EulerPhiInverse(m): RngIntElt -> RngIntElt"}
  - {"name": "EulerPhiInverse", "signature": "EulerPhiInverse(Q): RngIntEltFact -> RngIntElt"}
  - {"name": "FactoredEulerPhiInverse", "signature": "FactoredEulerPhiInverse(n): RngIntElt -> RngIntEltFact"}
  - {"name": "FactoredEulerPhiInverse", "signature": "FactoredEulerPhiInverse(Q): RngIntEltFact -> RngIntEltFact"}
  - {"name": "LegendreSymbol", "signature": "LegendreSymbol(n, m): RngIntElt, RngIntElt -> RngIntElt"}
  - {"name": "JacobiSymbol", "signature": "JacobiSymbol(n, m): RngIntElt, RngIntElt -> RngIntElt"}
  - {"name": "KroneckerSymbol", "signature": "KroneckerSymbol(n, m): RngIntElt, RngIntElt -> RngIntElt"}
  - {"name": "MoebiusMu", "signature": "MoebiusMu(n): RngIntElt -> RngIntElt"}
  - {"name": "MoebiusMu", "signature": "MoebiusMu(Q): RngIntEltFact -> RngIntElt"}
examples:
  - "ex-233f46"
---

# Arithmetic Functions

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

<a id="function-carmichaellambda-rngintelt"></a>
## `CarmichaelLambda(n): RngIntElt -> RngIntElt`

<a id="function-carmichaellambda-rnginteltfact"></a>
## `CarmichaelLambda(Q): RngIntEltFact -> RngIntElt`

<a id="function-carmichaellambda-tup"></a>
## `CarmichaelLambda(Q): [Tup] -> RngIntElt`

The Carmichael function $\lambda(n)$; its value equals the exponent of ${({{\mathbb{Z}}/n{\mathbb{Z}}})^*}$.

<a id="function-dickmanrho-fldreelt"></a>
## `DickmanRho(u): FldReElt -> FldReElt`

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

<a id="function-factoredcarmichaellambda-rngintelt"></a>
## `FactoredCarmichaelLambda(n): RngIntElt -> RngIntEltFact`

<a id="function-factoredcarmichaellambda-rnginteltfact"></a>
## `FactoredCarmichaelLambda(Q): RngIntEltFact -> RngIntEltFact`

<a id="function-factoredcarmichaellambda-tup"></a>
## `FactoredCarmichaelLambda(Q): [Tup] -> RngIntEltFact`

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

<a id="function-divisorsigma-rngintelt-rngintelt"></a>
## `DivisorSigma(i, n): RngIntElt, RngIntElt -> RngIntElt`

<a id="function-divisorsigma-rngintelt-rnginteltfact"></a>
## `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$.

<a id="function-numberofdivisors-rngintelt"></a>
## `NumberOfDivisors(n): RngIntElt -> RngIntElt`

<a id="function-numberofdivisors-rnginteltfact"></a>
## `NumberOfDivisors(Q): RngIntEltFact -> RngIntElt`

The number of divisors of the positive integer $n$. This is a special case of `DivisorSigma`.

<a id="function-sumofdivisors-rngintelt"></a>
## `SumOfDivisors(n): RngIntElt -> RngIntElt`

<a id="function-sumofdivisors-rnginteltfact"></a>
## `SumOfDivisors(Q): RngIntEltFact -> RngIntElt`

The sum of the divisors of the positive integer $n$. This is a special case of `DivisorSigma`.

<a id="function-eulerphi-rngintelt"></a>
## `EulerPhi(n): RngIntElt -> RngIntElt`

<a id="function-eulerphi-rnginteltfact"></a>
## `EulerPhi(Q): RngIntEltFact -> RngIntElt`

<a id="function-eulerphi-tup"></a>
## `EulerPhi(Q): [Tup] -> RngIntElt`

The Euler totient function $\phi(n)$; its value equals the order of ${({{\mathbb{Z}}/n{\mathbb{Z}}})^*}$.

<a id="function-factoredeulerphi-rngintelt"></a>
## `FactoredEulerPhi(n): RngIntElt -> RngIntEltFact`

<a id="function-factoredeulerphi-rnginteltfact"></a>
## `FactoredEulerPhi(Q): RngIntEltFact -> RngIntEltFact`

<a id="function-factoredeulerphi-tup"></a>
## `FactoredEulerPhi(Q): [Tup] -> RngIntEltFact`

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

<a id="function-eulerphiinverse-rngintelt"></a>
## `EulerPhiInverse(m): RngIntElt -> RngIntElt`

<a id="function-eulerphiinverse-rnginteltfact"></a>
## `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$.

<a id="function-factoredeulerphiinverse-rngintelt"></a>
## `FactoredEulerPhiInverse(n): RngIntElt -> RngIntEltFact`

<a id="function-factoredeulerphiinverse-rnginteltfact"></a>
## `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$.

<a id="function-legendresymbol-rngintelt-rngintelt"></a>
## `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.

<a id="function-jacobisymbol-rngintelt-rngintelt"></a>
## `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$.

<a id="function-kroneckersymbol-rngintelt-rngintelt"></a>
## `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$).

<a id="function-moebiusmu-rngintelt"></a>
## `MoebiusMu(n): RngIntElt -> RngIntElt`

<a id="function-moebiusmu-rnginteltfact"></a>
## `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.

<a id="example-ex-233f46"></a>
## `Example: Amicable Pairs of Integers (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
```
