Totient

Euler's totient function: the count of integers in 1..n coprime to n.

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaEuler's totient function↗MathWorldTotientFunction↗WikidataQ190026↗Encyclopedia of MathematicsEuler_function↗Britannicatopic/Euler-phi-function↗DLMF27.2.E7↗FungrimTotient✓↗Fungrim entryOEISA000010↗Wolfram LanguageEulerPhi!↗

Totient(n)count of integers in $[1,n]$ coprime to $n$, Euler's $\varphi(n)$.

SageMatheuler_phi(n)!↗SymPytotient(n)↗Oscareuler_phi(ZZ(n))Juliaeuler_phi(ZZ(n))

Typed signatures

Type	Package	Applies
(integer) -> integer	compute-engine	always
(number) -> integer	number-theoryreplaces compute-engine	always

Domain: Number theory

Details

• Also called Euler's phi function; central to RSA key generation and elementary number theory.
• Multiplicative: $\varphi(mn)=\varphi(m)\varphi(n)$ whenever $\gcd(m,n)=1$.
• For $n=p_1^{k_1}\cdots p_m^{k_m}$, $\varphi(n)=n\prod_i\left(1-\frac1{p_i}\right)$.
• Divisor sum identity: $\sum_{d\mid n}\varphi(d)=n$.
• $\varphi(0) = 0$, as in Wolfram; a list argument is threaded over element-wise.

Plot

Examples

Basic #

live ↗

In$\mathrm{Totient}(12)$Out$4$

live ↗

In$\mathrm{Totient}(36)$Out$12$

live ↗

In$\mathrm{Totient}(1)$Out$1$

live ↗

In$\mathrm{Totient}(10)$Out$4$

Scope #

$\varphi(0) = 0$, as in Wolfram

live ↗

In$\mathrm{Totient}(0)$Out$0$

Threads element-wise over a list, as Wolfram's Listable heads do

live ↗

In$\mathrm{Totient}(\bigl\lbrack2, 4, 6\bigr\rbrack)$Out$\bigl\lbrack1, 2, 2\bigr\rbrack$

Large integers: $\varphi(50!)$

live ↗

In$\mathrm{Totient}(50!)$Out$4\,218\,559\,200\,885\,839\,042\,679\,312\,107\,816\,703\,841\,788\,854\,953\,574\,400\,000\,000\,000\,000$

Negative $n$: $\varphi(-n)=\varphi(n)$

live ↗

In$\mathrm{Totient}(-10)$Out$4$

Applications #

RSA key setup: $\varphi(17\times23)=16\times22=352$

live ↗

In$\mathrm{Totient}(391)$Out$352$

Euler's theorem: $a^{\varphi(n)}\equiv1\pmod n$ when $\gcd(a,n)=1$. See PowerMod

live ↗

In$\mathrm{PowerMod}(7, \mathrm{Totient}(10), 10)$Out$1$

Properties #

$\sum_{d\mid n}\varphi(d)=n$, checked over the divisors of 12

live ↗

In$\mathrm{Totient}(1)+\mathrm{Totient}(2)+\mathrm{Totient}(3)+\mathrm{Totient}(4)+\mathrm{Totient}(6)+\mathrm{Totient}(12)$Out$12$

Multiplicative: $\varphi(mn)=\varphi(m)\varphi(n)$ when $\gcd(m,n)=1$, here for $4$ and $3$

live ↗

In$\mathrm{Totient}(12)=\mathrm{Totient}(4)\mathrm{Totient}(3)$Out$\mathrm{True}$

$\varphi(p)=p-1$ for a prime $p$

live ↗

In$\mathrm{Totient}(17)$Out$16$

$\varphi(p^k)=p^{k-1}(p-1)$: $3^3\cdot2=54$

live ↗

In$\mathrm{Totient}(81)$Out$54$

$\varphi(100)=100\cdot\frac12\cdot\frac45$

live ↗

In$\mathrm{Totient}(100)$Out$40$

$\varphi(35)=4\cdot6$ for coprime factors

live ↗

In$\mathrm{Totient}(35)$Out$24$

The Carmichael function always divides Euler's

live ↗

In$\mathrm{CarmichaelLambda}(8)\mid\mathrm{Totient}(8)$Out$\mathrm{True}$

For odd prime powers the two agree

live ↗

In$\bigl\lbrack\mathrm{Totient}(25), \mathrm{CarmichaelLambda}(25)\bigr\rbrack$Out$\bigl\lbrack20, 20\bigr\rbrack$

Gauss: $\sum_{d\mid n}\varphi(d)=n$

live ↗

In$\mathrm{DivisorSum}(15, \mathrm{Totient})=15$Out$\mathrm{True}$

Multiplicative over $1023=3\cdot11\cdot31$

live ↗

In$\mathrm{Totient}(1\,023)=\mathrm{Totient}(3)\mathrm{Totient}(11)\mathrm{Totient}(31)$Out$\mathrm{True}$

Only $1$ is coprime to $2$

live ↗

In$\mathrm{Totient}(2)$Out$1$

Known value · Wolfram MathematicalFunctionData, EulerPhi

A prime $p$ gives $p-1$

live ↗

In$\mathrm{Totient}(3)$Out$2$

Known value · Wolfram MathematicalFunctionData, EulerPhi

Odd numbers below 4: $1$ and $3$

live ↗

In$\mathrm{Totient}(4)$Out$2$

Known value · Wolfram MathematicalFunctionData, EulerPhi

Prime, so $4$

live ↗

In$\mathrm{Totient}(5)$Out$4$

Known value · Wolfram MathematicalFunctionData, EulerPhi

Only $1$ and $5$ are coprime to $6$

live ↗

In$\mathrm{Totient}(6)$Out$2$

Known value · Wolfram MathematicalFunctionData, EulerPhi

Prime, so $6$

live ↗

In$\mathrm{Totient}(7)$Out$6$

Known value · Wolfram MathematicalFunctionData, EulerPhi

Half the residues are odd: $2^{k-1}$ at $2^k$

live ↗

In$\mathrm{Totient}(8)$Out$4$

Known value · Wolfram MathematicalFunctionData, EulerPhi

$\varphi(p^2)=p(p-1)=6$

live ↗

In$\mathrm{Totient}(9)$Out$6$

Known value · Wolfram MathematicalFunctionData, EulerPhi

Prime, so $10$

live ↗

In$\mathrm{Totient}(11)$Out$10$

Known value · Wolfram MathematicalFunctionData, EulerPhi

Prime, so $12$

live ↗

In$\mathrm{Totient}(13)$Out$12$

Known value · Wolfram MathematicalFunctionData, EulerPhi

$\varphi(2)\varphi(7)=6$

live ↗

In$\mathrm{Totient}(14)$Out$6$

Known value · Wolfram MathematicalFunctionData, EulerPhi

$\varphi(3)\varphi(5)=8$

live ↗

In$\mathrm{Totient}(15)$Out$8$

Known value · Wolfram MathematicalFunctionData, EulerPhi

$2^4$ gives $2^3=8$

live ↗

In$\mathrm{Totient}(16)$Out$8$

Known value · Wolfram MathematicalFunctionData, EulerPhi

live ↗

In$\mathrm{Assuming}(p∈\mathbb{P}∧r∈ℤ∧r\gt0, \mathrm{FunctionExpand}(\mathrm{Totient}(p^{r})))$Out$\mathrm{Totient}(p^{{{r}}})$

About

Examples	34
Checked against	Wolfram Language 33 agree1 differSageMath 30 agree1 differSymPy 29 agree2 errormathlib4 8 agreeOscar 10 agree3 errorJulia 28 agree2 error
Crosswalk	WikipediaMathWorldWikidataEncyclopedia of MathematicsBritannicaDLMFFungrimFungrim entry ×16OEISWolfram LanguageSageMathSymPyOscarJulia

Implementation

mappedwolframpackages/oracle/src/mappings.ts

mappedsympypackages/oracle/src/mappings.ts

mappedsagepackages/oracle/src/mappings.ts

mappedoscarpackages/oracle/src/mappings.ts

mappedjuliapackages/oracle/src/mappings.ts

mappedmathlib4packages/oracle/src/mappings.ts

See also: MultiplicativeOrder, DivisorSigma