Totatives and cototatives

This article page is a stub, please help by expanding it.

The integers from 1 to $\scriptstyle n$ that are coprime to $\scriptstyle n$ are called the totatives of $\scriptstyle n$, while the remaining integers from 1 to $\scriptstyle n$ are called cototatives.

Euler's totient function is the number of totatives of $\scriptstyle n$, while Euler's cototient function is the number of cototatives of $\scriptstyle n$.

Totatives

The set of totatives of $\scriptstyle n$ is (see coprimality triangle)

$\{1\leq i\leq n~|~(n,i)=1\},$

where $\scriptstyle (n,i)$ is the greatest common divisor (GCD) of $\scriptstyle n$ and $\scriptstyle i.$

Thus, Euler's totient function is the cardinality of the set of totatives of $\scriptstyle n$:

$\varphi (n):=|\{1\leq i\leq n~|~(n,i)=1\}|.$

(Note that in the following table, most of the listed sequences are infinite, and thus we're referring to the subset of that sequence of all terms smaller than $n$).

Table of totatives

$\scriptstyle n$	Totatives of $\scriptstyle n$	A-number	Totient of $\scriptstyle n$ A000010
1	{1}		1
2	{1}		1
3	{1, 2}		2
4	{1, 3}		2
5	{1, 2, 3, 4}		4
6	{1, 5}		2
7	{1, 2, 3, 4, 5, 6}		6
8	{1, 3, 5, 7}		4
9	{1, 2, 4, 5, 7, 8}	A001651	6
10	{1, 3, 7, 9}		4
11	{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}		10
12	{1, 5, 7, 11}		4
13	{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}		12
14	{1, 3, 5, 9, 11, 13}		6
15	{1, 2, 4, 7, 8, 11, 13, 14}		8
16	{1, 3, 5, 7, 9, 11, 13, 15}		8
17	{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}		16
18	{1, 5, 7, 11, 13, 17}		6
19	{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}		18
20	{1, 3, 7, 9, 11, 13, 17, 19}		8
21	{1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}		12
22	{1, 3, 5, 7, 9, 13, 15, 17, 19, 21}		10
23	{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22}		22
24	{1, 5, 7, 11, 13, 17, 19, 23}		8
25	{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24}		20
26	{1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25}		12
27	{1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26}	A001651	18
28	{1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27}		12
29	{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28}		28
30	{1, 7, 11, 13, 17, 19, 23, 29}		8

The totatives yields the infinite sequence of finite sequences

{{1}, {1}, {1, 2}, {1, 3}, {1, 2, 3, 4}, {1, 5}, {1, 2, 3, 4, 5, 6}, {1, 3, 5, 7}, {1, 2, 4, 5, 7, 8}, {1, 3, 7, 9}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {1, 5, 7, 11}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, {1, 3, 5, 9, 11, 13}, ...}

whose concatenation gives:

A038566 Numerators in canonical bijection from positive integers to positive rationals <= 1: arrange fractions by increasing denominator then by increasing numerator.

{1, 1, 1, 2, 1, 3, 1, 2, 3, 4, 1, 5, 1, 2, 3, 4, 5, 6, 1, 3, 5, 7, 1, 2, 4, 5, 7, 8, 1, 3, 7, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 5, 7, 11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 3, 5, 9, 11, 13, ...}

A000010 Euler's totient function $\scriptstyle \varphi (n),\ n\,\geq \,1,$ (count of numbers up to $\scriptstyle n$ and coprime to $\scriptstyle n$).

{1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, ...}

All totients for $\scriptstyle n\,\geq \,3$ are even, since $\scriptstyle k$ is a totative if and only if $\scriptstyle n-k$ is a totative, while $\scriptstyle {\frac {n}{2}}$ obviously can't be a totative of $\scriptstyle n$.

Isolated totatives

An isolated totative, $\scriptstyle k$, of $\scriptstyle n$ is a positive integer which is less than and coprime to $\scriptstyle n$ and such that neither $\scriptstyle k-1$ nor $\scriptstyle k+1$ are coprime to $\scriptstyle n$.

A132952 $\scriptstyle a(n)$ = number of isolated totatives of $\scriptstyle n$.

{0, 1, 0, 2, 0, 2, 0, 4, 0, 4, 0, 4, 0, 6, 2, 8, 0, 6, 0, 8, 2, 10, 0, 8, 0, 12, 0, 12, 0, 8, 0, 16, 2, 16, 2, 12, 0, 18, 2, 16, 0, 12, 0, 20, 6, 22, 0, 16, 0, 20, 2, 24, 0, ...}

A132953 $\scriptstyle a(n)$ = the sum of the isolated totatives of $\scriptstyle n$.

{0, 1, 0, 4, 0, 6, 0, 16, 0, 20, 0, 24, 0, 42, 15, 64, 0, 54, 0, 80, 21, 110, 0, 96, 0, 156, 0, 168, 0, 120, 0, 256, 33, 272, 35, 216, 0, 342, 39, 320, 0, 252, 0, 440, 135, ...}

Cototatives

The set of cototatives of $\scriptstyle n$ is (see coprimality triangle)

$\{1\leq i\leq n~|~(n,i)>1\},$

where $\scriptstyle (n,i)$ is the greatest common divisor (GCD) of $\scriptstyle n$ and $\scriptstyle i.$

Thus, Euler's cototient function is the cardinality of the set of cototatives of $\scriptstyle n$:

${\overline {\varphi }}(n):=|\{1\leq i\leq n~|~(n,i)>1\}|.$

See also

• Jacobsthal function