## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# 7THE EULER PHI FUNCTION

The so-called Phi function, developed by the great Swiss mathematician, Leonard Euler, is involved in many theorems of number theory and other branches of mathematics.

## THE PHI FUNCTION

The number of positive integers less than n that are relatively prime to n is denoted ϕ(n). The first few values of this important function, called the Euler ϕ function, are given by ϕ(1) = 1, ϕ(2) = 1, ϕ(3) = 2, ϕ(4) = 2, ϕ(5) = 4, ϕ(6) = 2 (since only 1 and 5 are relatively prime to 6), ϕ(7) = 6, ϕ(8) = 4, ϕ(9) = 6, and ϕ(10) = 4.

Observe that if p is a prime, ϕ(p) = p − 1. To calculate ϕ(pk), notice that the numbers less than or equal to pk that are not relatively prime to it are the pk−1 multiples of p, namely, p, 2p, 3p

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required