Euler's totient function

In number theory, Euler's totient function counts the positive integers up to a given integer

n

{\displaystyle n}

that are relatively prime to

n

{\displaystyle n}

. It is written using the Greek letter phi as

φ

(

n

)

{\displaystyle \varphi (n)}

or

ϕ

(

n

)

{\displaystyle \phi (n)}

, and may also be called Euler's phi function. In other words, it is the number of integers

k

{\displaystyle k}

in the range

1

≤

k

≤

n

{\displaystyle 1\leq k\leq n}

for which the greatest common divisor

gcd

(

n

,

k

)

{\displaystyle \gcd(n,k)}

is equal to 1. The integers

k

{\displaystyle k}

of this form are sometimes referred to as totatives of

n

{\displaystyle n}

.

For example, the totatives of

n

=

9

{\displaystyle n=9}

are the six numbers 1, 2, 4, 5, 7 and 8. They are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, since

gcd

(

9

,

3

)

=

gcd

(

9

,

6

)

=

3

{\displaystyle \gcd(9,3)=\gcd(9,6)=3}

and

gcd

(

9

,

9

)

=

9

{\displaystyle \gcd(9,9)=9}

. Therefore,

φ

(

9

)

=

6

{\displaystyle \varphi (9)=6}

. As another example,

φ

(

1

)

=

1

{\displaystyle \varphi (1)=1}

since for

n

=

1

{\displaystyle n=1}

the only integer in the range from 1 to

n

{\displaystyle n}

is 1 itself, and

gcd

(

1

,

1

)

=

1

{\displaystyle \gcd(1,1)=1}

.

Euler's totient function is a multiplicative function, meaning that if two numbers

m

{\displaystyle m}

and

n

{\displaystyle n}

are relatively prime, then

φ

(

m

n

)

=

φ

(

m

)

φ

(

n

)

{\displaystyle \varphi (mn)=\varphi (m)\varphi (n)}

.

This function gives the order of the multiplicative group of integers modulo n (the group of units of the ring

Z

/

n

Z

{\displaystyle \mathbb {Z} /n\mathbb {Z} }

).