This site is supported by donations to The OEIS Foundation.

# Totatives and cototatives

(Redirected from Cototatives)

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

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

## Totatives

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

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

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

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

${\displaystyle \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 ${\displaystyle n}$).

Table of totatives
${\displaystyle \scriptstyle n}$ Totatives of ${\displaystyle \scriptstyle n}$ A-number Totient of ${\displaystyle \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 ${\displaystyle \scriptstyle \varphi (n),\ n\,\geq \,1,}$ (count of numbers up to ${\displaystyle \scriptstyle n}$ and coprime to ${\displaystyle \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 ${\displaystyle \scriptstyle n\,\geq \,3}$ are even, since ${\displaystyle \scriptstyle k}$ is a totative if and only if ${\displaystyle \scriptstyle n-k}$ is a totative, while ${\displaystyle \scriptstyle {\frac {n}{2}}}$ obviously can't be a totative of ${\displaystyle \scriptstyle n}$.

## Isolated totatives

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

A132952 ${\displaystyle \scriptstyle a(n)}$ = number of isolated totatives of ${\displaystyle \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 ${\displaystyle \scriptstyle a(n)}$ = the sum of the isolated totatives of ${\displaystyle \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 ${\displaystyle \scriptstyle n}$ is (see coprimality triangle)

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

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

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

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